Heap operations

The problem it solves

A stream of items arrives, and you repeatedly need the current extreme — the biggest, the cheapest, the soonest. Keeping the collection sorted buys far more than you need at far more than you can afford; keeping it unsorted makes every query a full scan. The heap is the deliberate compromise: a structure that maintains one promise only — every parent outranks its children — which is exactly enough to keep the extreme at the root, readable in O(1), while insertions and removals cost O(log n) apiece.

That one promise powers an outsized share of the standard library: priority queues, schedulers, top-k queries, merging k sorted streams, the frontier inside Dijkstra, Prim and A*, median maintenance with two opposing heaps, and heapsort. When a problem says “k largest”, “next cheapest”, or “process in priority order”, the heap is not one candidate among several — it is the presumptive answer, and the interview question is whether you know its two moves: sift up after a push, sift down after a pop.

The intuition — and where it breaks down

A corporate hierarchy where the only rule is that no one outranks their boss. A new hire enters at the bottom — the next open desk, not a position chosen by merit — and then promotion does the sorting: while the newcomer outranks their boss, they swap, and the climb stops at the first boss who genuinely outranks them. That is a push: placement by shape, correction by sifting, at most one root-ward path of swaps.

Removal is where the design gets clever. The root leaves — that is the whole point of asking — and the hole at the top is filled by the last element, the most junior desk, purely to keep the shape solid. That stand-in is almost certainly wrong for the job, so it sinks: while either subordinate outranks it, it swaps with the larger of the two — larger, necessarily, because whichever child rises becomes the boss of its sibling, and only the larger child outranks both. The sink stops when neither child outranks the stand-in.

Two places the picture misleads. First, people want the hierarchy to be sorted — it is not. Siblings are unordered; a node two levels down in one branch can outrank a node one level down in another. The heap promises a fast extreme, nothing about order among the rest — the player’s built-heap annotation says this at the exact moment the second level visibly disproves sortedness. Second, the tree picture hides the implementation’s best trick: because the shape is always complete (every level full, last level filled left to right), the whole tree packs into an array with children of slot i at 2i+1 and 2i+2 — no pointers, no allocation, arithmetic as structure. The drawing shows the tree because the tree is the intuition; the array is what ships.

Loading…

A walkthrough you can check

Push 4, 7, 2, 9 into a max-heap, then pop twice.

1. 4 — empty heap, becomes the root.
2. 7 — enters as 4’s left child (next slot), outranks 4 → one swap. Root 7.
3. 2 — enters as 7’s right child, does not outrank → zero swaps.
4. 9 — enters as 4’s left child (level 3), outranks 4 → swap; outranks 7 → swap. Root 9, two swaps: the full depth.
5. Pop → returns 9. The last element, 4, stands in at the root; children are 7 and 2; larger is 7, which outranks 4 → swap. 4’s new children: none that outrank. Heap: 7, 4, 2.
6. Pop → returns 7. Stand-in 2; child 4 outranks → swap. Heap: 4, 2.

Popped: 9, then 7 — the two largest, in order, each in at most log n swaps. Check yourself on the step the prediction prompt drills: in pop 5, why swap with 7 and not 2? Swap with 2 and the new arrangement puts 2 above 7 — the sibling instantly outranks its new parent. The larger-child rule is not a preference; it is the only correct choice.

The invariant

Heap property: every parent ≥ both children; shape property: the tree is complete. Push preserves both: shape by construction (next free slot), order by the sift — the induction is that a swap can only fix, never create, a violation, because the climbing value outranked the parent it displaced, and that displaced parent still outranks the other child it acquires (it outranked it before, and the child did not change). The climb stops precisely when the property holds along the whole path, and no other path was touched.

Pop’s invariant argument mirrors it downward: the stand-in may violate the property at the root, but nowhere else; each larger-child swap moves the single possible violation one level down (the risen child outranks both its old sibling and the sunk stand-in); the violation exits at a leaf or dissolves when the stand-in outranks both children. One violation, chased down one path — never a general repair.

The corollaries worth having ready: the root is always the maximum (property, applied transitively), and the array encoding is valid exactly because completeness never breaks — a hole anywhere would shift every index after it.

Complexity, derived

A complete tree of n nodes has height ⌊log₂ n⌋. A push’s sift climbs at most that path: O(log n), with the best case O(1) when the newcomer does not outrank its parent (common on random input — half of all values fail their first comparison). A pop’s sift sinks at most the same path: O(log n), with two comparisons per level (find the larger child, compare with it). Peek is O(1) forever.

The famous counterintuitive bound belongs here: building a heap by n pushes costs O(n log n), but building it by sifting down from the middle outward costs O(n) — half the nodes are leaves that sift zero levels, a quarter sift at most one, an eighth at most two; the sum Σ n/2^k · k converges to 2n. When an interviewer asks “can you build it faster than pushing n times”, this is the expected answer, with the geometric-series justification one sentence behind it.

What people get wrong

• Sifting down via the smaller child — the promoted child fails to outrank its sibling and the property breaks one step after it was “fixed”. The single most common heap bug, and the player’s pick-question exists to burn in the rule.
• Treating the heap as sorted — iterating the array and expecting order, or assuming the second-largest is a child of the root (it is one of the two children, but which one is unknowable without looking).
• Promoting a child instead of the last element on pop — repeatedly promoting the larger child leaves a hole that violates completeness, and the array encoding breaks silently.
• Index arithmetic off-by-ones — 1-based formulas (2i, 2i+1, i/2) used with 0-based arrays, or vice versa. Pick one convention and write it down before coding.
• Using a heap where a full sort was needed — extracting everything from a heap is heapsort at O(n log n); if you need everything ordered anyway, just sort.

Implementation notes

Production heaps are arrays, full stop: push appends then sifts up with parent (i−1)>>1; pop swaps root with last, shrinks, then sifts down choosing the larger child before comparing. Write the two sifts as loops, not recursion — the paths are short and the call overhead is real. The displayed sources are exactly this shape, with a tree drawn above them so the indices stay meaningful.

Three variations worth carrying. Build-heap: sift-down from ⌊n/2⌋−1 to 0 for the O(n) construction. Decrease-key / increase-key (Dijkstra’s friend): change the value, then sift in whichever direction the change points; if the heap cannot find arbitrary elements, use lazy deletion instead — push duplicates and discard stale pops, exactly as this site’s Dijkstra and Prim traces narrate. d-ary heaps: wider nodes mean shallower trees — fewer levels for sift-up-heavy workloads at the cost of more comparisons per level on the way down; d = 4 is a real-world sweet spot for cache lines.

Min-heap versus max-heap is one comparison flip; most standard libraries ship min-heaps (Python’s heapq) and negation is the standard adapter — an irritating convention worth knowing before the interview rather than during it.

The follow-up questions

Why does a heap fit in an array with no pointers? Completeness makes the level-order packing gapless, so structure becomes arithmetic: children at 2i+1 and 2i+2, parent at (i−1)>>1. No allocation, no pointer-chasing, ideal locality.

Why must sift-down use the larger child? The risen child becomes the parent of its sibling, so it must outrank both. Rising the smaller child places it above the larger — an instant violation one level below the “repair”.

Why is build-heap O(n)? Sift-down costs are bounded by height from the bottom: half the nodes sift 0, a quarter ≤1, an eighth ≤2 — the series sums to 2n. Pushing n times pays log-from-the-top instead, which genuinely is n log n.

How do two heaps maintain a running median? A max-heap of the lower half, a min-heap of the upper half, sizes kept within one: the median is a root (or the mean of both). Every insert is one push, possibly one transfer — O(log n) — and the question is a heap question wearing a statistics costume.