Remember
- The tree is complete, so it fits an array with no gaps and no pointers at all.
- Insert and extract each walk one root-to-leaf path, so both are O(log n).
- Building a heap from scratch is O(n), cheaper than inserting n values one at a time.
A complete tree where every parent outranks its children. Nothing is sorted, and nothing needs to be: you only ever promise that the best value is on top.
These values are in no order. Sift every parent down, starting from the last one, and the whole thing becomes a max heap.
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
2 sits above 7. What happens?
Answer: Sink one more. A heap needs the larger value above, so 2 sinks one level.
9 sits above 9. What happens?
Answer: Stop here. 9 already outranks both children, so nothing moves.
3 sits above 9. What happens?
Answer: Sink one more. A heap needs the larger value above, so 3 sinks one level.
3 sits above 8. What happens?
Answer: Sink one more. A heap needs the larger value above, so 3 sinks one level.
These values are in no order. Sift every parent down, starting from the last one, and the whole thing becomes a max heap.
Building a max heap from 6 unordered values by sifting each parent down, starting with the last parent.
Take 2, the parent at index 2. Everything below it is already a heap.
Sifting down from index 2, which holds 2. Both subtrees beneath it already satisfy the heap property.
Its left child 7 is larger, so 2 sinks and 7 takes its place.
Comparing 2 with its children. The left child 7 is larger, so the two swap.
2 has no children left, so it has reached the bottom.
2 is a leaf and cannot sink further.
Take 9, the parent at index 1. Everything below it is already a heap.
Sifting down from index 1, which holds 9. Both subtrees beneath it already satisfy the heap property.
9 is already larger than both children, so it stays.
Comparing 9 with its children. 9 outranks both children and has found its level.
Take 3, the parent at index 0. Everything below it is already a heap.
Sifting down from index 0, which holds 3. Both subtrees beneath it already satisfy the heap property.
Its left child 9 is larger, so 3 sinks and 9 takes its place.
Comparing 3 with its children. The left child 9 is larger, so the two swap.
Its left child 8 is larger, so 3 sinks and 8 takes its place.
Comparing 3 with its children. The left child 8 is larger, so the two swap.
3 has no children left, so it has reached the bottom.
3 is a leaf and cannot sink further.
A max heap, in 7 comparisons and 3 swaps. Building costs O(n), not O(n log n).
The array is now a max heap. The root holds 9, the largest value.
def sift_up(h, start):
i = start
while i > 0 and better(h[i], h[parent(i)]):
swap(h, i, parent(i))
i = parent(i)
def sift_down(h, size, start):
i = start
while True:
best = best_of(h, size, i, left(i), right(i))
if best == i:
return
swap(h, i, best)
i = bestfunction siftUp(h, start) {
let i = start;
while (i > 0 && better(h[i], h[parent(i)])) {
swap(h, i, parent(i));
i = parent(i);
}
}
function siftDown(h, size, start) {
let i = start;
while (true) {
const best = bestOf(h, size, i, left(i), right(i));
if (best === i) return;
swap(h, i, best);
i = best;
}
}fun siftUp(h: IntArray, start: Int) {
var i = start
while (i > 0 && better(h[i], h[parent(i)])) {
swap(h, i, parent(i))
i = parent(i)
}
}
fun siftDown(h: IntArray, size: Int, start: Int) {
var i = start
while (true) {
val best = bestOf(h, size, i, left(i), right(i))
if (best == i) return
swap(h, i, best)
i = best
}
}This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.
An LSM-tree holds data in many sorted runs at once, and both a range scan and a compaction have to emit the merged key order across all of them. RocksDB keeps one iterator per run in a binary heap ordered by each iterator's current key, so producing the next key overall costs log k instead of checking all k runs. After a pop that iterator advances and is pushed back, which is the insert-and-extract cycle running continuously.
gzip, PNG and HTTP's deflate encoding all build a Huffman code by repeatedly taking the two least frequent symbols and merging them into a new node. zlib does this with an explicit heap in trees.c: it heapifies the symbol frequencies once, then pops twice and pushes the merged node back. A heap fits because the algorithm only ever needs the current minimum of a set that keeps changing under it.
CPython's asyncio keeps every callback scheduled for a future time in a heap ordered by deadline, while callbacks that are already due wait in a plain queue. On each turn the loop reads the earliest deadline off the top to decide how long the selector may block, then pops whatever has come due. Fully sorting thousands of pending timers would be wasted work, because the loop only ever asks which one fires next.
The standard libraries shipped with GCC, Clang and MSVC all sort with introsort: quicksort until the recursion goes deeper than about 2 log n, then heapsort for whatever is left of that range. Quicksort can be pushed to O(n squared) by an unlucky or hostile input, while heapsort has no bad input and needs no extra memory, so it is the safety net behind the O(n log n) worst-case guarantee. Heapsort is this structure used twice over: build the heap in place, then repeatedly swap the top to the end and shrink the heap by one.
Heapify does not insert n times. It starts at the last parent and sifts down toward the leaves, and sift-down work depends on how far a node sits from the bottom, not from the top. Half the nodes are leaves and move nowhere, a quarter move at most one level, an eighth at most two, and that series sums to less than n. Build the same heap by inserting values one at a time and the bound becomes O(n log n) in the worst case, because a value inserted at depth d can sift up all d levels and most nodes are deep.
The tree has to stay complete, or the array gets a hole and the index arithmetic stops working. Promoting the better child, then its better child, does restore the ordering, but the empty slot travels down with the promotions and ends at whatever leaf they run out on, which is almost never the last slot in the array. Live values sit after that gap, so the tree is no longer complete. The last element is the only one that can leave without a hole, so it goes to the root and one sift-down repairs the ordering it broke.
The only promise is that a parent beats its children, so reading the array left to right tells you almost nothing: the second best is a child of the root, at index 1 or 2, but the third could be in several places. Finding an arbitrary value costs O(n), which is why a heap is useless as a lookup structure. It is also why Dijkstra cannot simply lower a key that is already queued - there is no way to locate it without a side map from value to index. The usual workaround is lazy deletion: push the item again at its new priority and ignore any entry whose priority no longer matches when it pops.
In a 0-based array the children of i are at 2i + 1 and 2i + 2 and the parent is at (i - 1) / 2. Many textbooks store the heap 1-based instead, where the same relations are 2i, 2i + 1 and i / 2, and mixing the two conventions is the classic heap bug. The root is where it bites: sift-up has to stop at index 0, and in Python (0 - 1) // 2 floors to -1, which silently wraps to the last element instead of stopping. The i > 0 guard in the code above exists for exactly that reason.
Backtracking