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.
A min heap of 6 values. Add 1.
The player pauses before each decision in this run and asks what happens next. Here are all 2, with their answers.
1 sits under 7. What happens?
Answer: Climb one more. A heap needs the smaller value above, so 1 climbs.
1 sits under 2. What happens?
Answer: Climb one more. A heap needs the smaller value above, so 1 climbs.
A min heap of 6 values. Add 1.
A min heap with 6 values and 2 at the root. Inserting 1.
1 goes into the next free slot, index 6. That keeps the tree complete, but it is probably in the wrong place.
1 is added at index 6 as the next leaf, which keeps the tree complete.
1 is smaller than its parent 7, so they swap.
Comparing 1 with its parent 7. They swap and 1 moves up one level.
1 is smaller than its parent 2, so they swap.
Comparing 1 with its parent 2. They swap and 1 moves up one level.
It reached the root, so it is the smallest value in the heap.
The value reached the root and is the smallest in the heap.
1 is in place after 2 comparisons. One path from a leaf to the root is O(log n).
The heap is valid again. The root holds 1.
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