Appearance
4.16 — Heaps & Priority Queues
A hospital emergency room does not treat patients in arrival order. It treats the most urgent one next. New arrivals can jump the queue. Nobody ever asks "who is the third most urgent patient" — the only question that matters is "who is next".
That is the priority queue: a collection where you insert items with a priority and always remove the most urgent one. And that one-question restriction is what lets it be so much cheaper than a sorted structure.
A sorted array could do it: insert in the right place (O(n) because of the shift), remove the front (O(n) because of the shift, or O(1) if you keep the smallest at the end). A balanced tree could do it: O(\log n) for everything, plus pointer chasing and a lot of code. The heap does insert and remove-minimum in O(\log n), peek-minimum in O(1), uses a plain array with no pointers at all, and fits in about thirty lines.
1. The heap property: much weaker than sorted, and that is the point
A min-heap is a complete binary tree where every node's value is less than or equal to both of its children's.
Read that carefully against the BST rule from Chapter 4.13.1. A BST says left-subtree-smaller and right-subtree-larger, which forces a total ordering. A heap says only parent smaller than children, with no rule at all about how the two children compare to each other.
The weakness of the rule is what buys the speed. A sorted array has to know the exact position of everything. A heap only has to know that nothing smaller than the root exists — a much cheaper claim to maintain. And it is exactly the claim the priority queue needs.
The array trick. Because the tree is complete, it can be flattened into an array with no wasted slots and no pointers:
ts
const parent = (i: number) => (i - 1) >> 1; // (1)
const left = (i: number) => 2 * i + 1; // (2)
const right = (i: number) => 2 * i + 2;- Integer division by 2 after subtracting 1. Node 5's parent is index 2.
- Node 2's children are indices 5 and 6.
No node objects, no allocation per element, and the elements sit next to each other in memory so traversal is cache-friendly (Chapter 1.6). This is the same implicit-tree trick the segment tree used in Chapter 4.13.4, and it only works because the tree is complete — a BST cannot do it, because its gaps would leave the array full of holes.
2. Sift up and sift down: the two repair operations
Every heap operation is "break the rule in one specific place, then repair it by walking one path".
ts
class MinHeap {
private a: number[] = [];
peek(): number | undefined { return this.a[0]; } // (1) O(1)
push(value: number): void {
this.a.push(value); // (2)
this.siftUp(this.a.length - 1);
}
private siftUp(i: number): void {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p] <= this.a[i]) break; // (3) rule holds — stop
[this.a[p], this.a[i]] = [this.a[i], this.a[p]]; // (4) swap with parent
i = p;
}
}
pop(): number | undefined {
if (this.a.length === 0) return undefined;
const top = this.a[0]; // (5)
const last = this.a.pop()!; // (6)
if (this.a.length > 0) { this.a[0] = last; this.siftDown(0); } // (7)
return top;
}
private siftDown(i: number): void {
const n = this.a.length;
while (true) {
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < n && this.a[l] < this.a[smallest]) smallest = l; // (8)
if (r < n && this.a[r] < this.a[smallest]) smallest = r;
if (smallest === i) break; // (9)
[this.a[i], this.a[smallest]] = [this.a[smallest], this.a[i]];
i = smallest;
}
}
}- The minimum is at index 0 by the heap rule, so peeking is a single array read.
- Push puts the new value at the end, which is the only place a complete tree can grow without leaving a gap. That may violate the rule between it and its parent, and nowhere else.
- Walk up while the new value is smaller than its parent. The moment the parent is smaller, stop — everything above is already correct, because it was correct before and we only made one subtree's minimum smaller.
- Swap and continue up. At most \log_2 n swaps, since that is the height.
- and 6. Pop is the clever one. The answer is at index 0, but you cannot just delete index 0 — that leaves a hole at the root. So take the last element (whose removal leaves no hole, since the tree fills left to right) and move it to the root.
- The root is now almost certainly too big, so sift it down.
- Compare against both children and pick the smaller one. This is the step people get wrong: swapping with the left child unconditionally can move a value that is still larger than the right child, breaking the rule.
- If neither child is smaller, the rule holds everywhere below and we stop.
Both operations walk one root-to-leaf path, so both are O(\log n) — with a very small constant, because each step is one or two comparisons and a swap inside a contiguous array.
A max-heap is the same code with the comparisons flipped. In practice most libraries take a comparator, and you get a max-heap by passing one that reverses the order. In JavaScript, which ships no heap at all, the common trick for a max-heap is to push negated numbers into a min-heap.
3. Heapify: building a heap in O(n), not O(n \log n)
Given an unsorted array, you could push each element one at a time: n pushes at O(\log n) each, so O(n \log n).
There is a better way, and the analysis behind it is one of the most instructive in this Part.
ts
function heapify(a: number[]): void {
for (let i = (a.length >> 1) - 1; i >= 0; i--) siftDown(a, i); // (1)
}- Start at the last node that has a child and sift down, working backwards to the root. Everything past index
n/2 - 1is a leaf, and a leaf is already a valid one-node heap, so those need no work at all.
Going backwards is what makes it correct: when you sift down node i, both of its subtrees are already valid heaps, because you processed them first.
Why this is O(n). The naive count says n/2 nodes times \log n work each, giving O(n \log n). That over-counts badly, because siftDown's cost is the node's height, and almost every node is near the bottom where the height is tiny.
Count by level in a heap of n nodes:
| Level from bottom | Node count | Max sift-down steps | Total work |
|---|---|---|---|
| 0 (leaves) | n/2 | 0 | 0 |
| 1 | n/4 | 1 | n/4 |
| 2 | n/8 | 2 | 2n/8 |
| 3 | n/16 | 3 | 3n/16 |
| … | … | … | … |
The total is \sum_{h \ge 1} \frac{n}{2^{h+1}} \cdot h, and pulling out n gives n \sum \frac{h}{2^{h+1}}. That sum converges to 1, so the total is less than n. Half the nodes do zero work; a quarter do at most one swap. The expensive nodes exist, but there are almost none of them.
The transferable lesson, stated in Chapter 4.1 and worth repeating here: do not multiply the worst-case per-item cost by the item count when the cost varies with position. Sum it properly instead. This is the single most common place where a correct algorithm gets an incorrect complexity.
4. Heapsort, and why nobody uses it
Heapsort follows immediately: heapify the array in O(n), then repeatedly swap the root with the last unsorted element and sift down over a shrinking region.
ts
function heapSort(a: number[]): void {
heapify(a); // (1) O(n) — becomes a MAX-heap
for (let end = a.length - 1; end > 0; end--) {
[a[0], a[end]] = [a[end], a[0]]; // (2) largest goes to its final place
siftDown(a, 0, end); // (3) restore over the shrunk region
}
}- Build a max-heap so the largest is at the root.
- Swap it to the end of the unsorted region — that is exactly where the largest belongs in the final sorted order.
- Sift the displaced value down, treating everything from
endonward as already sorted and off-limits.
O(n \log n) worst case guaranteed, O(1) extra space, and the array ends up sorted in place. On paper that beats both merge sort (needs O(n) extra space) and quicksort (has an O(n^2) worst case).
In practice heapsort is rarely the default, for two reasons.
Cache behaviour. Sift-down jumps from index i to 2i+1, which for a large array means jumping to a completely different part of memory. Quicksort scans linearly through contiguous regions, which the CPU prefetcher loves. On large arrays quicksort commonly runs two to three times faster despite doing more comparisons — the Chapter 4.1 warning about the machine model, again.
Instability. Heapsort is not stable: equal elements can be reordered, because the swap in step 2 moves an element across the whole array. Merge sort is stable, which matters when you sort by one field and expect an earlier sort by another field to survive.
Where heapsort is used is as the safety net inside introsort (Chapter 4.10): C++'s std::sort runs quicksort, watches the recursion depth, and if it exceeds about 2 \log n — meaning quicksort is hitting its bad case — it switches to heapsort for that subrange. You get quicksort's speed with heapsort's worst-case guarantee.
5. The three problem shapes a heap solves
Shape one: top-k. "The 10 largest of a billion values."
Sorting is O(n \log n) and holds everything in memory. A heap of size k does it in O(n \log k) with O(k) memory:
ts
function topK(nums: number[], k: number): number[] {
const heap = new MinHeap(); // (1) a MIN-heap, for the LARGEST k
for (const n of nums) {
heap.push(n);
if (heap.size() > k) heap.pop(); // (2) evict the smallest
}
return heap.toArray();
}- The counter-intuitive line. To keep the k largest, use a min-heap. Its root is the smallest of the ones you have kept, which is precisely the one to throw away when a better candidate arrives.
- The heap never exceeds k+1 elements, so each push and pop costs \log k, not \log n.
With a billion values and k = 10, that is 10^9 \times \log_2 10 \approx 3.3 \times 10^9 operations with 10 items in memory, against sorting's 10^9 \times 30 operations with a billion items in memory. The memory difference is what makes it possible at all.
This generalises to streaming: you can maintain the top k of an infinite stream, because you never store more than k items. Chapter 4.29 covers what to do when even k is too large and you accept approximate answers.
Shape two: k-way merge. Merging k sorted lists — sorted files, sorted shards from different database partitions, sorted runs on disk when the data is too big for memory.
Put the first element of each list into a heap tagged with which list it came from. Pop the smallest, emit it, and push the next element from that list. The heap never holds more than k items, so merging n total elements across k lists costs O(n \log k).
This is how external sorting works and how a distributed query engine merges results from many shards, so it is a pattern that carries real weight rather than an interview curiosity.
Shape three: "always process the currently cheapest option". This is Dijkstra's algorithm (Chapter 4.19), and it is also A*, Prim's minimum spanning tree, Huffman coding (Chapter 1.8), and event-driven simulation where the heap holds future events keyed by time. In every case the heap answers the same question: of everything I could do next, which is cheapest?
6. What a plain heap cannot do
It cannot find an arbitrary element. There is no ordering between siblings, so searching for a specific value is O(n) — you must scan the whole array. A heap is not a searchable structure.
It cannot change an element's priority efficiently, on its own. Dijkstra's algorithm wants to say "the distance to node X just improved, move it up the heap". To do that you need to know where X currently sits, and the heap does not know. The fix is an indexed heap: a side hash map from element to its current array index, updated on every swap. That is real extra code, which is why most implementations use the lazy deletion trick instead — push the improved entry as a duplicate, and when popping, skip any entry whose recorded distance no longer matches the best known one. It wastes a little memory and is dramatically simpler.
It cannot merge with another heap cheaply. Merging two binary heaps of size n is O(n). Structures that specialise in this exist — the binomial heap and the Fibonacci heap merge in O(\log n) and O(1) respectively. The Fibonacci heap also gives O(1) amortized decrease-key, which improves Dijkstra's theoretical bound to O(E + V \log V). In practice its constant factors are so large that binary heaps beat it on essentially all real inputs, which is why it is famous in textbooks and rare in code. Knowing that a structure is theoretically better and practically worse, and being able to say why, is a genuinely senior answer.
What the interviewer will push on
"You want the k largest elements. Do you use a min-heap or a max-heap?" A min-heap of size k, and the reason is what they are testing: the root is the weakest of your current keepers, which is exactly the one to evict. People answer max-heap by reflex and then cannot explain how eviction works.
"Why is building a heap O(n) when each sift-down is O(\log n)?" Because the cost is the node's height, and half the nodes are leaves with height 0, a quarter have height 1, and so on. The sum \sum \frac{n}{2^{h+1}} h converges to less than n. This is the question that separates memorisation from understanding.
"Heapsort is O(n \log n) worst case and in place. Why is quicksort usually the default?" Cache locality — sift-down jumps to 2i+1 and thrashes the cache, while quicksort scans contiguously. Also stability. Then mention introsort, which uses heapsort only as the fallback when quicksort's recursion goes too deep.
"How does Dijkstra update a node's priority when it finds a shorter path?" Either an indexed heap with a map from element to array position, maintained through every swap, or lazy deletion where you push a duplicate and skip stale entries on pop. Naming both and saying which is simpler is the strong answer.
"Find the median of a stream of numbers." Two heaps: a max-heap of the lower half and a min-heap of the upper half, kept within one element of the same size. The median is one root, or the average of both roots. Insert is O(\log n), query is O(1). This is asked often enough to be worth having ready.
One thing to volunteer: say what the heap cannot do. "It gives me the minimum in O(1) but it cannot search, so if I also need lookups I would pair it with a hash map." Naming the limitation before it is discovered signals that you know the structure rather than the recipe.
Recall
- A heap enforces only parent ≤ children, with no ordering between siblings — far weaker than a BST, which is exactly why it is cheaper.
- Because the tree is complete, it flattens into a plain array with
parent = (i-1)/2andchildren = 2i+1, 2i+2— no pointers, no allocation per element, good cache behaviour. pushappends and sifts up;popreturns the root, moves the last element to the root, and sifts down, always comparing against both children. Both O(\log n);peekis O(1).- Heapify is O(n), not O(n \log n), because a node's cost is its height and almost every node is a leaf — the sum \sum \frac{n}{2^{h+1}}h converges below n.
- Top-k uses a min-heap of size k, because its root is the weakest keeper and therefore the right one to evict. Cost O(n \log k) with O(k) memory, which works on streams.
- A heap cannot search (O(n)), cannot change a priority without an indexed heap or lazy deletion, and cannot merge cheaply.
Self-test: Why does pop move the last element to the root rather than promoting a child? · Why is heapify O(n) and inserting n items O(n \log n), when both build the same structure? · Min-heap or max-heap for the k largest, and why? · Why does quicksort usually beat heapsort despite the worse worst case? · How do you maintain a running median with two heaps?
Next: 4.17 is the "which is next" problem set — top-k, merging sorted streams, and the two-heap trick that keeps a running median in O(\log n).