Algocraft · Theory
Heaps: a tree hiding inside an array
A heap gives you instant access to the "best" element in a collection — the largest, or the smallest, whichever you need — while still supporting fast inserts and removals. The trick that makes it fast: it isn't built from node objects and pointers at all. It's stored as a plain array, and a couple of tiny index formulas make that array behave exactly like a tree.
01 · Foundation
The heap-order invariant
A heap is a complete binary tree — every level is filled left to right, with no gaps, except possibly the last level, which fills from the left. On top of that shape, it enforces one ordering rule everywhere:
- Max-heap — every parent's value is ≥ both of its children's values.
- Min-heap — every parent's value is ≤ both of its children's values.
Follow that rule all the way up and the single most extreme value in the whole collection ends up at the root — index 0. That's the entire reason a heap is useful: peeking at the "best" element is always just one lookup away.
heap[1] to be the second-biggest value, and don't expect a left-to-right scan to come out in order — that's exactly what heaps do not give you for free.
02 · Representation
It's just an array
Because a heap is always a complete tree, there are never any gaps to worry about — which means you never need real node objects with explicit left/right/parent pointers. You can lay every node out left-to-right, level by level, into one flat array, and recover the tree structure purely from arithmetic on the index. For a node stored at 0-indexed array position i:
- Left child — index
2*i + 1 - Right child — index
2*i + 2 - Parent — index
floor((i - 1) / 2)
That's it — no traversal, no pointer-chasing. Given any index, you know exactly where its relatives live in constant time.
[20, 12, 18, 9, 10, 15, 16] is a valid max-heap. The dashed lines show the index formulas at work — e.g. index 1 (value 12)'s children live at 2*1+1=3 and 2*1+2=4 (values 9, 10); index 5 (value 15)'s parent lives at floor((5-1)/2)=2 (value 18). No pointers, just arithmetic.
03 · Method
A repeatable framework
- 1 Pick max-heap or min-heapNeed fast access to the largest element? Max-heap. The smallest? Min-heap. This one choice decides every comparison you write from here on.
-
2
Represent it as a plain arrayNo node class, no pointers. Use the index formulas above — left
2i+1, right2i+2, parentfloor((i-1)/2)— to move around the implicit tree. - 3 Insert: append, then sift upPush the new value onto the end of the array. While it violates the heap-order invariant with its parent, swap them — and keep going, checking the new parent each time, not just once.
- 4 Extract root: swap, shrink, sift downSwap the root with the very last element, shrink the array by one, then sift the new root down — repeatedly swap it with whichever child would restore the invariant, until it settles into a valid spot.
- 5 Top-K: cap the heap's sizeFor "keep the K best" problems, don't hold everything — cap the heap at size K, and on each new element only replace the current worst-of-the-K if the newcomer is better.
04 · Worked example
Inserting 15 into [20, 12, 18, 9, 10]
[20, 12, 18, 9, 10] is itself a valid max-heap: 20 ≥ 12, 18 ✓ and 12 ≥ 9, 10 ✓. Insert appends the new value at the end, at index 5, giving [20, 12, 18, 9, 10, 15] — then sifts it up.
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| value | 20 | 12 | 18 | 9 | 10 | 15 |
The new element (outlined, index 5) has parent index floor((5-1)/2) = 2 — that's the cell shaded as the parent, value 18. Since 15 < 18, the max-heap invariant already holds. No swap happens, and the insert is done after a single comparison: [20, 12, 18, 9, 10, 15].
To see the sift-up actually move something, imagine inserting 25 instead. It lands at index 5 next to parent index 2 (18); 25 > 18, so they swap and 25 moves to index 2. Index 2's parent is index floor((2-1)/2) = 0 (20); 25 > 20, so they swap again and 25 reaches the root, where it stops (no parent left to check). Final array: [25, 12, 20, 9, 10, 18] — still a valid max-heap, reached in exactly two swaps along one root-to-leaf path.
05 · Complexity
How to reason about time & space
- Peek at the root —
O(1). It's alwaysheap[0]. - Insert (sift-up) —
O(log n). The new element only ever moves along a single path from a leaf toward the root, and because the tree is complete, its height is alwaysO(log n). - Extract-root (sift-down) —
O(log n), for the same reason: one root-to-leaf path, bounded by the tree's height.
n sift-downs at O(log n) each, but that overcounts the work badly: most nodes live near the bottom of the tree and only need a short sift-down (a leaf needs zero), while only a handful of nodes near the root ever sift through the full height. Summed across every level, the total work collapses to O(n) — a classic case where the naive per-node bound doesn't reflect the real total.
06 · Before you start coding
Common mistakes
- Mixing up the parent/child index formulas — the ones on this page (
2i+1,2i+2,floor((i-1)/2)) assume a 0-indexed array. A 1-indexed array uses different formulas (2i,2i+1,floor(i/2)) — mixing the two conventions is a classic off-by-one bug. - Sifting for only one swap instead of continuing until the invariant actually holds — after swapping, keep checking the new parent (on insert) or the new children (on extract) rather than stopping after a single exchange.
- Assuming a heap is fully sorted end-to-end — the invariant only guarantees a parent versus its own children, not any ordering between elements in different branches or at the same level.
- Forgetting to shrink the array after extracting the root — leaving the old last element duplicated at the end instead of removing it corrupts the size and the shape of the tree.
- Reaching for a heap when you actually need everything in fully sorted order — a heap only guarantees fast access to the current extreme, one element at a time. If you need the whole collection in order, a heap alone isn't the right tool.
07 · Try it