Heap
⏱️ ~3-minute bite · solve the sandbox to master
5-Year-Old Metaphor
— The physical, real-world picture. No jargon.🏥 A hospital waiting room where the sickest patient is always seen first — but the other seats aren't sorted.
The core idea
A heap is a binary tree with one rule: every parent is more extreme than its children. In a min-heap, every parent is smaller (sickest first). In a max-heap, every parent is larger (highest salary at the top of the org chart).
The top always holds the extreme value. But the rest? Not fully sorted — just roughly ordered. That's the trade-off: you get O(log n) access to the extreme element without paying the O(n log n) cost of a full sort.
Min-Heap
Hospital triage: root = sickest patient. Every nurse only needs to look at the top. When a patient is treated, the next sickest bubbles up automatically.
Use for: Dijkstra, A*, task schedulers, finding kth smallest
Max-Heap
Corporate org chart: root = highest earner. Every manager earns more than their direct reports. Useful when you want the maximum fast.
Use for: HeapSort, finding kth largest, streaming median
Why an array, not a tree?
A complete binary tree maps perfectly to an array with no pointers needed. For index i:
This is 0-based. Some textbooks use 1-based (left = 2i, right = 2i+1, parent = ⌊i/2⌋). The interview bug: mixing up 0-based and 1-based index math.
Interactive Sandbox
— Move something, see it react instantly.Array representation
Tree visualization
⚠️ Gotcha
0-based index math: parent = Math.floor((i-1)/2). Not (i/2). Off-by-one breaks the whole tree.
💡 Insight
Sift-up only travels the height of the tree — O(log n). The rest of the heap stays untouched.
Challenge
Explore all 5 heap patterns. (1 / 5 explored)
Why Should I Care?
— The exact interview question + the bug it kills.Q: Heap vs sorted array for priority queue?
A sorted array gives O(1) access to the min/max — just read the first or last element. But insertion is O(n) because you must shift elements to maintain order. A heap gives O(log n) insert and O(log n) extract. When you're doing many insertions and extractions (a scheduler, Dijkstra's open set), the heap wins massively.
Q: Why O(n) build heap but O(n log n) insert n times?
Building bottom-up (heapify): most nodes are near the leaves where sift-down travels height 0 or 1. Only the root travels log n. The geometric sum works out to O(n).
Inserting one-by-one: every insertion can sift up through the full height — O(log n) each × n insertions = O(n log n). Same result, different constant. For large n, bottom-up is 2× faster in practice.
Q: When to use heap vs sort?
Sort everything when you need global order. Use a heap when you only need the top k elements, or when data arrives as a stream and you can't sort ahead of time. Heap + k = O(n log k). Full sort = O(n log n). When k is small (e.g. k=10 from 10M items), heap is orders of magnitude faster.
Bug: 0-based vs 1-based index math
| 1 | // 0-based (standard JS arrays) ✅ |
| 2 | const left = 2 * i + 1; |
| 3 | const right = 2 * i + 2; |
| 4 | const parent = Math.floor((i - 1) / 2); |
| 5 | |
| 6 | // 1-based (some textbooks) — mixing these is the bug ❌ |
| 7 | // left = 2*i, right = 2*i+1, parent = Math.floor(i/2) |
| 8 | // If your heap gives wrong answers, check this first. |
Complexity reference
| Operation | Time | Space |
|---|---|---|
| Insert (sift-up) | O(log n) | O(1) |
| Extract min/max | O(log n) | O(1) |
| Peek min/max | O(1) | O(1) |
| Build heap (heapify) | O(n) | O(1) |
| Heap sort | O(n log n) | O(1) |
| Kth largest (heap of size k) | O(n log k) | O(k) |
The Deep Dive
— Spec refs, engine internals, the minutiae.Binary heap index math — the full picture
A complete binary tree of height h has 2^(h+1) - 1 nodes. Nodes at depth d start at index 2^d - 1 (0-based). Leaves occupy roughly half the array (indices ⌊n/2⌋ to n-1). This is why heapify starts at index ⌊n/2⌋ - 1 and works backwards — it skips all the leaves, which have nothing to sift.
Sift-up vs sift-down — when each is used
Sift-up
- Used on INSERT: new element appended at end, bubbles toward root
- Compare with parent only, single path to root
- At most log n comparisons
Sift-down
- Used on EXTRACT and HEAPIFY: root replaced, falls toward leaves
- Compare with both children, pick the smaller (min-heap)
- At most 2 log n comparisons (both children each level)
Sift-down does twice the comparisons — important for cache analysis. HeapSort uses sift-down exclusively, which is why its constant is larger than MergeSort's.
Priority queue in JavaScript (no built-in)
JS/TS has no built-in heap. You implement one with an array. The minimal viable min-heap:
| 1 | class MinHeap { |
| 2 | private h: number[] = []; |
| 3 | |
| 4 | push(val: number) { |
| 5 | this.h.push(val); |
| 6 | this._siftUp(this.h.length - 1); |
| 7 | } |
| 8 | |
| 9 | pop(): number { |
| 10 | const top = this.h[0]; |
| 11 | const last = this.h.pop()!; |
| 12 | if (this.h.length > 0) { |
| 13 | this.h[0] = last; |
| 14 | this._siftDown(0); |
| 15 | } |
| 16 | return top; |
| 17 | } |
| 18 | |
| 19 | peek() { return this.h[0]; } |
| 20 | size() { return this.h.length; } |
| 21 | |
| 22 | private _siftUp(i: number) { |
| 23 | while (i > 0) { |
| 24 | const p = (i - 1) >> 1; // same as Math.floor((i-1)/2) |
| 25 | if (this.h[p] <= this.h[i]) break; |
| 26 | [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; |
| 27 | i = p; |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | private _siftDown(i: number) { |
| 32 | const n = this.h.length; |
| 33 | while (true) { |
| 34 | let s = i; |
| 35 | const l = 2*i+1, r = 2*i+2; |
| 36 | if (l < n && this.h[l] < this.h[s]) s = l; |
| 37 | if (r < n && this.h[r] < this.h[s]) s = r; |
| 38 | if (s === i) break; |
| 39 | [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; |
| 40 | i = s; |
| 41 | } |
| 42 | } |
| 43 | } |
Real uses in production
- Dijkstra / A* — min-heap on (cost, node) drives the frontier. Without it, you'd scan all unvisited nodes each step: O(V²) vs O((V+E) log V).
- Task schedulers — Node.js's event loop, OS process scheduling, React's concurrent scheduler all use priority queues. Tasks with highest priority are dequeued first.
- Streaming median — maintain two heaps: max-heap of the lower half, min-heap of the upper half. Keep them balanced. Median is always the root of one or the average of both. O(log n) per insert, O(1) median query.
- Top-k reporting — leaderboards, trending topics, log anomaly detection. Min-heap of size k: discard anything smaller than the current kth largest.
Fibonacci heap — theory vs practice
Fibonacci heaps achieve decrease-key in O(1) amortized, making Dijkstra O(E + V log V) vs O((V+E) log V) with a binary heap. Theoretically superior on dense graphs.
In practice? Rarely used. The constant factors are enormous — pointer-heavy, cache-unfriendly, complex to implement correctly. For most real graphs, a binary heap or even a simple array beats a Fibonacci heap due to cache behavior. Know the theory for interviews; use binary heap in code.
Related patterns
- Two Heaps — streaming median, task partitioning
- Monotonic Deque — sliding window maximum in O(n) — different from heap but similar "always have the extreme fast" goal
- Segment Tree — range queries beyond just min/max (sum, GCD) with O(log n) update
- Order Statistics Tree — find kth element in O(log n) for a fully dynamic set
Interview Questions
— Real questions from real interviews — with answers.A heap is a complete binary tree satisfying the heap property — insert and extract-min/max are O(log n); peek is O(1).
Maintain a min-heap of size k — the root is always the k-th largest seen so far.
Push the head of each list into a min-heap, then repeatedly extract the min and advance that list's pointer.
Max-heap for the lower half, min-heap for the upper half — balance them after each insert so sizes differ by at most 1.
Heap is O(log n) insert/extract and O(1) peek — BST adds O(log n) arbitrary delete and ordered traversal but with higher constants.
Memory Game
— Quick quiz — lock the concept in long-term memory.What is the time complexity of extracting the minimum from a min-heap?