What a heap is
You're running a hospital ER. Patients arrive in any order, each with an urgency score, and you must always treat the most urgent one next while new patients keep streaming in. Keeping the list sorted forces a re-sort on every arrival (
O(n log n)); leaving it unsorted forces a full scan to find the top (O(n)). But you never need the whole thing sorted — only the single most urgent one.A heap is a binary tree kept loosely ordered by one rule: every parent is more urgent than its children (a max-heap) — or less, for a min-heap. That rule guarantees the extreme element always sits at the root, instantly readable. It's a triage queue: you never re-sort everyone, you just always pull the top next. Because the tree stays balanced (a complete tree), it packs neatly into an array and each change touches just one path.
Quick check
In a min-heap, which element is always at the root?
Answer it in the interactive lesson to keep your progress.
How a heap is stored (parent, left, right)
Here is the key insight: a heap needs no node objects or pointers — it lives in a plain array, and the tree shape is pure index math. For the value at index : Take the min-heap
[1, 3, 6, 5, 9, 8]. The root 1 sits at index 0, so its children are at indices 1 and 2 (3 and 6); the value 9 at index 4 has its parent at index 1 (3). Prove it to yourself:const arr = [1, 3, 6, 5, 9, 8]; // a min-heap as a flat array
const i = 0; // start at the root
console.log('left child:', arr[2 * i + 1]); // 3
console.log('right child:', arr[2 * i + 2]); // 6
const c = 4; // the value 9
console.log('parent of index 4:', arr[(c - 1) >> 1]); // 3Quick check
In a heap stored as an array, the children of index i live at…
Answer it in the interactive lesson to keep your progress.
The core operations
A heap supports a small set of moves (shown here on a min-heap):
- peek — read the root (the min/max).
O(1). - push (insert) — drop the new value at the bottom and let it bubble up past any smaller parent until it fits.
- pop (remove-root) — take the root, move the last element to the top, and let it sink down past its smaller child until order is restored.
- size — how many items.
Each push/pop fixes one root-to-leaf path — height
log n. In the animation, watch how little of the tree each operation touches: an inserted value swaps with its parent only, hop by hop up one path; a sinking value swaps with its smaller child only, down one path. Everything off that path never moves — that is where the O(log n) comes from.This section has a step-by-step animation in the interactive lesson.
const heap = new MinHeap();
[5, 2, 8, 1, 9, 3].forEach((n) => heap.push(n));
console.log(heap.peek()); // 1 (smallest is always on top)
console.log(heap.size); // 6 (count of items)
console.log(heap.pop()); // 1 (remove and return the top)
console.log(heap.peek()); // 2 (next smallest rises up)Quick check
Min-heap [1, 3, 6, 5, 9, 8]. You pop the root. Predict what happens first.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Min vs. max mix-up. JS gives you neither by default. For a max-heap via a min-heap, negate the values (or invert the comparator) — forgetting this quietly returns the wrong extreme.
- A heap is not sorted. Only the root is guaranteed; the rest is partially ordered. Do not read the array as a sorted list.
- Rebuilding instead of updating. Re-heapifying from scratch on every change throws away the whole point — push and pop in
O(log n)instead.
Quick check
Reading a heap's array left to right gives…
Answer it in the interactive lesson to keep your progress.
Take it further — the top-K largest
Because pop always hands back the current extreme, a heap makes "top-K" almost free: put everything in a max-heap, then pop
k times to get the k largest in order. Here are the top 3 of [3, 1, 7, 9, 2, 8] — first the values are heapified, then three pops peel off 9, 8, 7 in order.In the animation, watch each pop trigger the same two-beat move from the last section: last value to the top, sink down one path. Three pops, three short paths — no full sort of the six values ever happens.
This section has a step-by-step animation in the interactive lesson.
const values = [3, 1, 7, 9, 2, 8];
const maxPq = new MaxHeap();
values.forEach((v) => maxPq.push(v));
const top3 = [maxPq.pop(), maxPq.pop(), maxPq.pop()];
console.log(top3); // [9, 8, 7]Quick check
Predict the cost of top-K via a heap of all n values: build once, pop k times.
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, every operation follows the tree's height,
log n:| Operation | Cost | Why |
|---|---|---|
| peek the root | O(1) | it is always at index 0 |
| push | O(log n) | bubble up one path |
| pop | O(log n) | sink down one path |
| build (heapify) | O(n) | cheaper than n pushes |
Storing
n values takes O(n) space.Key takeaways:
- A heap keeps just enough order: the extreme is always at the root.
- push/pop are
O(log n), peek isO(1)— far better than re-sorting. - Stored as an array (children at
2i+1/2i+2), partially ordered — not sorted.
This serves "give me the current best/worst" over a changing collection. These classics each get their own lesson later (no need to know them yet): Kth largest / top-K (just above), merge K sorted lists (a heap of the K front elements), and Dijkstra's shortest path (a min-heap of frontier distances). Next up in order: Trie — a tree of letters for instant prefix search.