What is a heap?
A heap is a tree stored flat in an array where every parent is bigger than its children — or, for a min-heap, smaller. That one invariant is the whole idea: it never sorts the tree fully, it only guarantees the root. Reading the current best is O(1); putting a new value back in the right place after a change is O(log n).
- Heap invariant
- Every parent compares a fixed way — always ≥ (max-heap) or always ≤ (min-heap) — to its children
- Sift-up
- Insert at the next open slot, then swap upward with the parent until the invariant holds again
- Sift-down
- Move a value to the root, then swap downward with the larger (or smaller) child until it settles
Why a heap at all?
Picture a company org chart where every manager earns more than their direct reports. You don't know the full company-wide ranking of salaries — you'd have to walk the whole chart for that — but you always know who's at the top without looking anywhere else.
That's the trade a heap makes. It gives up full ordering everywhere in exchange for O(1) access to the best value and O(log n) upkeep every time something changes — which is exactly the shape "get the current best, repeatedly" problems need.
No full ranking exists — just parent ≥ children, everywhere in the tree.
What kinds of problems does it solve?
Four common shapes. Two are about keeping the invariant intact — sift-up on insert, sift-down on removal — and two are about the payoff: always having the current best on hand without sorting everything else.
Insert and sift up
A new value goes in at the next open slot — the bottom of the tree. If it's bigger than its
parent, swap them, and repeat from the new position. It stops the moment the parent is
bigger, or it reaches the root.
Two swaps carry 95 from a leaf all the way to the root.
Remove the root and sift down
Removing the root leaves a hole. Move the last leaf into it, then repeatedly swap with the
larger child (max-heap) until the value beats both children or hits a leaf.
The promoted leaf sinks until both children are smaller than it.
Track the top k with a bounded heap
Keep a heap of exactly k items — the k largest seen so far, using a min-heap
so the smallest of the k sits at the root. A new value only matters if it beats the root; then
it replaces it and the heap re-settles.
The root is always the weakest of the k kept — the one to evict next.
Priority queue for "what's next"
A priority queue is just a heap keyed by priority. Dijkstra's frontier is the classic case: every discovered node sits in the heap by distance, and the algorithm is nothing more than "pop the smallest, visit it, push its neighbors" on repeat.
Never a full sort — just "give me the next best" on repeat.
Two types
Underneath, it's really only two shapes: a max-heap that keeps the largest value on top, and a min-heap that keeps the smallest. The mechanics — sift-up, sift-down — never change, only the direction of the comparison.
Max-heap
Every parent is greater than or equal to both of its children, at every level, not just
the root. heap[0] is always the maximum of everything in the heap.
function siftUp(heap: number[], index: number): void {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (heap[parent] >= heap[index]) break; // invariant already holds
[heap[parent], heap[index]] = [heap[index], heap[parent]];
index = parent;
}
}
Min-heap
Every parent is less than or equal to both of its children. heap[0] is always the
minimum — the shape used for "smallest remaining" problems like Dijkstra's frontier.
function siftDown(heap: number[], index: number, size: number): void {
while (true) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let smallest = index;
if (left < size && heap[left] < heap[smallest]) smallest = left;
if (right < size && heap[right] < heap[smallest]) smallest = right;
if (smallest === index) break; // invariant already holds
[heap[index], heap[smallest]] = [heap[smallest], heap[index]];
index = smallest;
}
}
Where it works — and where it breaks
The invariant only ever promises one thing: the root is the best value. It says nothing about the order of anything else in the array — that's the assumption that quietly breaks code.
Works: repeatedly asking for the best
Pop the root, promote the last leaf, sift it down — one bounded walk down the tree restores the invariant, so every pop is O(log n) and the new root is provably still the max of what remains.
Every pop stays O(log n) because the invariant guarantees the fix.
Breaks: assuming the array is fully sorted
Only heap[0] is guaranteed. heap[1] is not "the second-largest" — it's just one of
the root's two children, and the true second-largest could just as easily be heap[2].