Sorting a million values to take the smallest three is doing an enormous amount of work you throw away. A heap is the structure for when you only ever want the next one.
The promise#
A min heap keeps one rule: every node is smaller than its children.
1
/ \
3 5
/ \ /
8 4 9
Note what this does not say. It says nothing about left against right. 3 and 5 are not in any order, and 8 sits below 3 while 4 also sits below 3. The heap does not care.
Keeping only this weaker promise is exactly why a heap is cheap to maintain. The one thing you are guaranteed is that the smallest value in the whole structure is at the root.
A max heap is the same with the comparison flipped.
It is secretly an array#
A heap is always a complete tree: every level is full except possibly the last, which fills left to right. That regularity means it needs no node objects and no pointers at all. It lives in a plain array:
index: 0 1 2 3 4 5
value: [1, 3, 5, 8, 4, 9]
with the relationships worked out by arithmetic:
- children of
i:2i + 1and2i + 2 - parent of
i:(i - 1) / 2, rounded down
Index 1 holds 3; its children are at 3 and 4, holding 8 and 4. Which matches the drawing.
No pointers, no allocation per node, and everything sits next to each other in memory, which is genuinely faster to walk.
Adding: sift up#
Put the new value at the end of the array, then swap it upward while it is smaller than its parent.
Adding 2:
[1, 3, 5, 8, 4, 9, 2] 2 goes at the end, parent is 5
[1, 3, 2, 8, 4, 9, 5] 2 < 5, swap
2's parent is now 1, and 2 > 1, so stop
At most one swap per level, so O(log n).
Removing the smallest: sift down#
The root is the answer. Take it. Now the root is empty, so move the last value into it and swap it downward with its smaller child until it settles.
[1, 3, 2, 8, 4, 9, 5] take 1
[5, 3, 2, 8, 4, 9] last value 5 moves to the root
[2, 3, 5, 8, 4, 9] children 3 and 2; 2 is smaller, swap
5's children are 9; 5 < 9, stop
Again one swap per level, so O(log n).
The price list#
| what you do | cost |
|---|---|
| look at the smallest | O(1) |
| add a value | O(log n) |
| remove the smallest | O(log n) |
| find some arbitrary value | O(n) |
build a heap from n values at once | O(n) |
That last one surprises people: building a heap all at once is linear, not n log n. Most nodes are near the bottom and barely move.
And notice the O(n) for finding an arbitrary value. A heap is not a search structure. Asking it "do you contain 7" means looking at everything.
What it buys you#
The k largest of n values. Keep a min heap of size k. For each value, if it is bigger than the heap's smallest, remove that and add this. Cost O(n log k) and memory O(k), instead of sorting everything at O(n log n) and holding it all.
That memory point matters. It works on a stream of a billion values that never fit in memory at once.
A priority queue. A queue serves the oldest; a priority queue serves the most important. That is a heap, and it is the engine inside Dijkstra's shortest path algorithm and most task schedulers.
A running median. Two heaps facing each other, a max heap for the lower half and a min heap for the upper half, keeping their sizes within one. The median is then at one or both roots.
Common mistakes#
- Expecting a heap to be sorted. Only the root is guaranteed.
- Using a max heap for the k largest values. You want a min heap of size k, so the easiest to evict is the weakest one you are keeping.
- Searching a heap for an arbitrary value.
- Forgetting that most standard libraries give you a min heap, so getting a max heap means negating your values or supplying a reversed comparison.