Binary Heap
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. The root 1 is the smallest value, so it is the one that leaves.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 2, with their answers.
6 sits above 2. What happens?
Answer: Sink one more. A heap needs the smaller value above, so 6 sinks one level.
6 sits above 6. What happens?
Answer: Stop here. 6 already outranks both children, so nothing moves.
How it runs, step by step
A min heap. The root 1 is the smallest value, so it is the one that leaves.
A min heap with 7 values. The root holds 1, the smallest value.
1 leaves. The last leaf 6 jumps to the root, which keeps the tree complete but almost certainly breaks the heap.
1 is removed. The last leaf 6 takes the root position, keeping the tree complete.
Its right child 2 is smaller, so 6 sinks and 2 takes its place.
Comparing 6 with its children. The right child 2 is smaller, so the two swap.
6 is already smaller than both children, so it stays.
Comparing 6 with its children. 6 outranks both children and has found its level.
1 is out and 2 is the new smallest, after 3 comparisons. One root-to-leaf path is O(log n).
The heap is valid again with 2 at the root.
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.
Topics covered
Related
Where this is used
DatabasesRocksDB compaction and range scans
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.
CompressionHuffman trees in DEFLATE
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.
RuntimesTimers in the asyncio event loop
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.
Standard librariesHeapsort as the fallback inside std::sort
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.
Why it works this way
Why building a heap is O(n) when every insert is O(log n)
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.
Why extract-top moves the last leaf to the root instead of promoting a child
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 array is not sorted, and you cannot search it
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.
The index arithmetic, and the off-by-one hiding in it
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.
Read more
- Binary heapWikipedia
- heapq - heap queue algorithmPython docs · docs.python.org
- HeapsortWikipedia
- Dijkstra on sparse graphscp-algorithms
- Heap visualisedUSF