Heaps: The Complete Guide
A binary search tree promises you a total order: left < node < right, everywhere. A heap promises far less — only that a parent beats its children. Nothing about siblings, nothing about cousins, nothing about subtrees relative to each other.
That weakness is the entire point. A promise that weak can be maintained by a tree that is always perfectly balanced, which means the shape is fully determined by the element count, which means the tree needs no pointers at all — it collapses into a flat array where 2i+1 and 2i+2 replace child links. No allocation, no rebalancing, no per-node overhead, and the nodes every operation touches sit at the front of the array where the cache keeps them.
sift_up and sift_down from memory with the correct bounds guards; you can say instantly whether a problem wants a min-heap or a max-heap and defend it; you can explain why bottom-up build is O(n); you can write Dijkstra with lazy deletion and say what the stale check is for; and you know three situations where a heap is the wrong answer. This series is ordered to get you there.
The One Rule Behind Everything
If you remember one sentence from all seventeen parts, make it this:
The root of your heap should be the element you are most willing to throw away.
Every direction question resolves against it. Want the k largest? The thing you would discard is the smallest of what you have kept — so, a min-heap. Sorting ascending in place with heapsort? Each round you evict the largest remaining into the rightmost free slot — so, a max-heap. Regret greedy? You want to revoke your most expensive commitment — so, a max-heap of costs. Direction mistakes are the single most common heap bug in interviews, and this sentence eliminates all of them.
The Roadmap
Foundations
The structure itself: shape, encoding, invariant, and the two repair routines that constitute nearly all of the code.
- 1. Complete Binary Trees & the Array Encoding 18 min — why completeness forces one shape per n, and how that removes pointers entirely.
- 2. The Heap Property, push & pop 20 min — the one-line invariant, an induction proof that the root is a global minimum, and why pop costs more than push.
- 3. Sift-Up, Sift-Down & Why They Are Correct 22 min — hole-punching instead of swaps, loop invariants, and the three bugs that break most hand-rolled heaps.
- 4. Building a Heap in O(n) 19 min — Floyd's algorithm and the summation showing why bottom-up is linear but top-down is not.
- 5. std::priority_queue & the Heap Algorithms 20 min — the comparator convention read as a rule rather than memorised, and the four things the adaptor cannot do.
Core Techniques
The patterns that cover essentially every heap problem you will be asked.
- 6. Heapsort 21 min — O(n log n) worst case in O(1) space, why it still loses to quicksort, and its real job inside introsort.
- 7. Top-K & the Bounded Heap Pattern 20 min — why the k largest needs a min-heap, and O(k) space that works on streams.
- 8. K-Way Merge 21 min — O(N log k) merging, external sorting, LSM compaction, and the sequential-merge trap.
- 9. Two Heaps & the Running Median 20 min — two heaps facing each other, the push-shuttle-rebalance insertion, and the sliding-window variant.
- 10. Scheduling, Intervals & the Sweep 22 min — Meeting Rooms II, sweep line as the alternative, and jumping the clock instead of ticking it.
- 11. Greedy Algorithms Powered by a Heap 23 min — Huffman, Dijkstra, Prim, and the regret pattern that undoes an earlier choice.
Advanced Structures
What to do when the plain binary heap is not enough.
- 12. Indexed Heaps, decrease-key & Lazy Deletion 22 min — reaching an arbitrary element, exactly or lazily, and which you should actually ship.
- 13. D-ary Heaps & Cache Behaviour 19 min — widening the tree so children share a cache line, and why d = 4 usually wins.
- 14. Mergeable Heaps 23 min — leftist, skew, binomial, Fibonacci and pairing heaps, and why the theoretically best one is the one nobody uses.
Mastery
- 15. Pitfalls: Comparators, Overflow & Invalidation 21 min — strict weak ordering, dangling references, and a table of cases where a heap is the wrong tool.
- 16. Interview Pattern Catalog 18 min — the seven patterns, their recognition signals, and a decision table.
- 17. Capstone: Build a Discrete-Event Simulator 20 min — a project, a four-tier problem catalog, and a self-assessment checklist.
Complexity Cheat Sheet
| Operation | Cost | Note |
|---|---|---|
top | O(1) | read index 0 |
push | O(log n) | often O(1) in practice |
pop | O(log n) | usually the full descent |
| build from n items | O(n) | bottom-up, not n pushes |
| heapsort | O(n log n) | O(1) extra space, unstable |
| top-k | O(n log k) | O(k) space, streaming |
| k-way merge | O(N log k) | O(k) space |
| Dijkstra | O(E log V) | O(E log E) with lazy deletion |
| search / contains | O(n) | no ordering to guide it |
| merge two heaps | O(n) | use a pairing heap for O(1) |
When a Heap Is the Wrong Answer
| You need | Use instead | Why |
|---|---|---|
| Membership tests | unordered_set | heap search is O(n) |
| k-th smallest, once, in memory | nth_element | O(n) average, beats O(n log k) |
| Sliding window extreme | monotonic deque | O(n) versus O(n log n) |
| Frequent arbitrary erase | std::set | heaps have no erase |
| Both min and max | two heaps or std::set | one heap serves one end |
| Small fixed priority range | bucket queue | O(1) instead of O(log n) |
| Sorted iteration | std::sort | heap order is not sorted order |
Related Reading
- C++ STL: Heaps & Priority Queues — the full standard-library surface, comparators over structs and lambdas, and the algorithm family in depth.
- DSA: Linked Lists — the companion series on pointer discipline; merging sorted lists overlaps directly with Part 8.
- Amortized Analysis — the technique behind the O(n) build proof and the binomial-heap bounds.
Start with Part 1.