HeapEdit

Operations

Core operations

• insert O(log n)
• extract O(log n)
  • extract min (for a min heap)
  • extract max (for a max heap)

Other operations

• heapify (ie. batch insert) O(n)
• delete O(log n)

Example applications

• Dijkstra’s shortest path algorithm: O(m log n)
• Heapsort: O(n log n)

In general, any algorithm that requires a priority queue.

See also

• Wikipedia article on heaps: http://en.wikipedia.org/wiki/Heap_(data_structure)