A tree with no pointers
A binary heap is a complete binary tree — every level full except the last, which fills left to right — which means it can be stored in an array with no pointers at all. The arithmetic above is the entire structure.
The invariant is weaker than a search tree’s: every node is smaller than its children (for a min-heap). Nothing is said about left versus right, so a heap is not sorted and cannot be searched. It only ever answers one question, and it answers it in O(1): what is the smallest thing?
index: 0 1 2 3 4 5 6
value: [1, 3, 2, 7, 5, 4, 9]
1 parent of i → (i - 1) >> 1
/ \ left of i → 2i + 1
3 2 right of i → 2i + 2
/ \ / \
7 5 4 9Push: sift up
Put the new item at the end and swap it upwards while it is smaller than its parent. It can rise at most the height of the tree, which is log n — and because a heap is always complete, the height is always log n. There is no degenerate case.
push(item) {
this.items.push(item); // at the end, keeping it complete
let i = this.items.length - 1;
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.items[parent] <= this.items[i]) break;
[this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];
i = parent;
}
}Pop: sift down
The root leaves, the last item takes its place to keep the tree complete, and then it sinks — swapping with its smaller child each time, because that child has to become the new parent of the other one.
pop() {
const top = this.items[0];
const last = this.items.pop();
if (this.items.length) {
this.items[0] = last; // the last item goes to the top…
let i = 0;
for (;;) { // …and sinks to its place
const left = 2 * i + 1;
const right = left + 1;
let smallest = i;
if (left < this.items.length && this.items[left] < this.items[smallest]) smallest = left;
if (right < this.items.length && this.items[right] < this.items[smallest]) smallest = right;
if (smallest === i) break;
[this.items[smallest], this.items[i]] = [this.items[i], this.items[smallest]];
i = smallest;
}
}
return top;
}Top-k: the pattern worth remembering
O(n log k) instead of O(n log n), and O(k) memory instead of O(n). At a million items and k = 10 that is about 3.3 million operations against 20 million — and, more importantly, it works on a stream: you never have to hold the million items at all.
Using a min-heap to find the largest items is the part that feels backwards, and it is the whole trick: the top of the heap is the weakest of your current champions, which is exactly the one to evict.
/* the obvious way: sort everything. O(n log n), and O(n) memory */
const top10 = [...items].sort((a, b) => b - a).slice(0, 10);
/* a MIN-heap of size 10: the smallest of the ten best is at the top,
so anything smaller than it can be rejected in one comparison. O(n log k) */
const heap = new MinHeap();
for (const x of items) {
if (heap.size < 10) heap.push(x);
else if (x > heap.peek()) { heap.pop(); heap.push(x); }
}Where heaps show up
One more fact worth knowing: building a heap from an existing array by sifting down from the middle is O(n), not O(n log n) — most of the nodes are near the bottom and barely move. Pushing n items one at a time is the O(n log n) way.
| Use | Why a heap |
|---|---|
| Dijkstra and A* | Always expand the nearest unvisited node — the next lesson |
| Task schedulers, timers | The next thing to run is the smallest deadline |
| Merging k sorted streams | A heap of the k current heads, O(n log k) |
| Heapsort | Heapify, then pop n times: O(n log n), in place, no bad case |
| Median of a stream | Two heaps, a max-heap and a min-heap, balanced against each other |