Heaps and priority queues
The array layout and heap invariant, sift-up and sift-down, linear-time bulk build, and the top-k and scheduling patterns that make a priority queue the right tool.
A tree stored in an array
A binary heap is a complete binary tree with one rule: every parent is less than or equal to its children (a min-heap). Because it is complete, it fits in a flat array with no pointers.
index: 0 1 2 3 4 5 6
value: [1, 3, 2, 7, 4, 5, 9]
1
/ \
3 2
/ \ / \
7 4 5 9
parent(i) = (i - 1) / 2
left(i) = 2i + 1
right(i) = 2i + 2- Only the root is guaranteed to be the minimum; the rest of the array is not sorted.
- The array form gives excellent cache behaviour compared with a pointer tree.
- Equal elements may be ordered arbitrarily — heap sort and priority queues are not stable.
Sift up, sift down, build
import heapq
h = []
heapq.heappush(h, 5) # sift up: O(log n)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = heapq.heappop(h) # sift down: O(log n) -> 1
# linear-time bulk build from an existing list
nums = [9, 4, 7, 1, 8]
heapq.heapify(nums) # O(n), not O(n log n)
# max-heap: negate the values
maxh = [-x for x in [3, 1, 4]]
heapq.heapify(maxh)
largest = -heapq.heappop(maxh)
# tuples let you carry a payload; the first element is the priority
tasks = [(5, "low"), (1, "urgent")]
heapq.heapify(tasks)
priority, name = heapq.heappop(tasks)Bulk build is O(n) because most nodes are leaves: sifting down from the last internal node does almost no work for the bottom levels, and the total is a convergent series.
Top-k and scheduling
# Top-k: keep a bounded min-heap of size k
def top_k(stream, k):
heap = []
for score, item in stream:
if len(heap) < k:
heapq.heappush(heap, (score, item))
elif score > heap[0][0]:
heapq.heapreplace(heap, (score, item)) # pop + push in one step
return sorted(heap, reverse=True)| Approach | Time | Memory | When to use |
|---|---|---|---|
| Sort everything | O(n log n) | O(n) | Small n, or when you need full order anyway |
| Bounded heap of size k | O(n log k) | O(k) | Streaming top-k with small k |
| Quickselect | O(n) average | O(1) extra | One-off k-th element on an array in memory |
| Merge pre-sorted runs | O(n log k) | O(k) | Log files or shards each already sorted |
💡
A priority queue is not a sorted list. If you need to enumerate everything in order, extract repeatedly and accept O(n log n); if you need to peek at the minimum and update priorities in place, use an indexed heap, which libraries often leave out for you to build.
FAQ
Can I change the priority of an item already in the heap?
Not in the basic API. Push the new entry and mark the old one stale with a version number, then discard stale entries on pop — the standard lazy-deletion pattern.
Why is heapq a min-heap when I usually want the largest?
Min-heaps make extraction of the smallest trivial. For maximums, negate the key, or store a tuple with a negated first element.
Related
Amortised analysis: what operations really cost Probabilistic structures: Bloom filters and skip lists
Last refreshed 2026-09-18.