Binary heap and priority queue
Top-k problems, scheduling by priority, Dijkstra's algorithm, and merging sorted lists.
| Time | Peek O(1); push and pop O(log n); build from n items O(n) |
|---|---|
| Space | O(n) |
Why it costs this much
The tree is complete, so its height is about log n. Sifting an item up or down moves it at most that many levels.
Code
import heapq
h = []
heapq.heappush(h, 5) # O(log n): sift up at most log n levels
smallest = h[0] # O(1): the root
heapq.heappop(h) # O(log n): sift down at most log n levels
heapq.heapify(items) # O(n): faster than n separate pushesPython is the baseline example used across the site.
Common pitfalls
Searching for an arbitrary value is O(n). Python's heapq is a min-heap with no decrease-key; negate values to get a max-heap.
Operation by operation
| Operation | Best | Average | Worst | Space |
|---|---|---|---|---|
| Binary heap peek | O(1) | O(1) | O(1) | O(1) |
| Binary heap push | O(1) | O(1) for random keys | O(log n) | O(1) extra |
| Binary heap pop | O(1) if all keys are equal | O(log n) | O(log n) | O(1) extra |
| Build a heap from n items (heapify) | O(n) | O(n) | O(n) | O(1) in place |
Binary heap peek. Reads the root only. Finding any other element is O(n).
Binary heap push. Average assumes random keys. The new item usually stays near the bottom. Plan for O(log n) in interviews unless you can justify the average case.
Binary heap pop. The last item moves to the root and sifts down. Removing an arbitrary item is O(n) to find, then O(log n) to fix.
Build a heap from n items (heapify). Bottom-up sift down, not n separate pushes. Pushing n items one at a time is O(n log n).