HeapEdit
Redirected from Heaps
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)
- Dijkstra’s shortest path algorithm: O(m log n)
- Heapsort: O(n log n)
In general, any algorithm that requires a priority queue.