Notifications
Last 30 Days
No notifications
Last 30 Days
No notifications
A heap is a complete binary tree where every parent is smaller (min-heap) or larger (max-heap) than its children.
| Operation | Time | Description |
| Insert | O(log n) | Add at bottom, bubble UP |
| Extract Min/Max | O(log n) | Remove root, bubble DOWN |
| Peek | O(1) | View root element |
| Heapify (build) | O(n) | Build heap from array |
A heap is the data structure you reach for whenever you need "the smallest" or "the largest" *over and over* — task schedulers, Dijkstra, Huffman codes, the median of a stream, top-K processing, every priority queue you've ever used. It's the cleanest example of how a clever invariant turns a simple array into something that gives you the extreme element in O(1) and updates in O(log n).
A heap is a complete binary tree stored in a flat array that maintains one rule:
| Variant | Heap property | Root contains |
| Min-heap | parent ≤ both children | the minimum |
| Max-heap | parent ≥ both children | the maximum |
That's the whole rule. Note what it does not say: there's no ordering between siblings, no ordering across subtrees. A heap is a much weaker invariant than a BST — and that weakness is the whole point. It's cheap to maintain.
`
Max-heap Min-heap
50 1
/ \ / \
30 40 3 2
/ \ / / \ /
10 20 35 5 8 4
`
Imagine a hospital queue where the most critical patient is always seen next. New patients keep arriving with different priorities. You don't need a fully sorted list — you only need "who's worst right now?" and "remove that person, give me the next worst". That's a min-heap with severity as the key.
1. Confusing heap with BST. A heap has no ordering between siblings — \heap[5]\ could be larger or smaller than \heap[6]\. You can't binary-search a heap. The only thing you're guaranteed is the root.
2. Off-by-one in the index math. Parent of \i\ is \(i-1)/2\ for 0-indexed arrays. If you copy a textbook formula written for 1-indexed arrays (\i/2\), everything will silently corrupt for the first few elements.
3. Forgetting to sift after replacing the root. "Pop" isn't "shift the array". You move the last element to position 0, then sift it down. People often delete from the front and end up with O(n) per pop.
4. Using \heapq\ for a max-heap directly. Python only ships a min-heap. For max behaviour, push \-x\ and negate on pop.
5. Assuming JS has one. It doesn't. You write your own or pull a library. Don't ship \array.sort()\ inside a loop and call it a "priority queue".
6. Calling buildHeap O(n log n). It's actually O(n) — see the proof below. This is one of the most common interview gotchas.
A complete binary tree maps perfectly to an array with no wasted slots and no pointers. For node at index \i\ (0-indexed):
| Quantity | Formula |
| Parent | \(i - 1) >> 1\ |
| Left child | \2*i + 1\ |
| Right child | \2*i + 2\ |
| Is leaf? | \i >= n / 2\ |
| Last non-leaf | \(n / 2) - 1\ |
That's it. Heaps need zero pointers and have perfect cache locality — one of the reasons they're so fast in practice.
Insert — O(log n)
`js
push(val) {
this.heap.push(val); // tack onto the end
let i = this.heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.heap[p] <= this.heap[i]) break; // min-heap: parent already smaller
[this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
i = p;
}
}
`
The new element bubbles up at most height = \log₂ n\ levels.
Pop — O(log n)
`js
pop() {
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length) {
this.heap[0] = last; // overwrite root
let i = 0, n = this.heap.length;
while (true) {
const l = 2*i + 1, r = 2*i + 2;
let smallest = i;
if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
if (smallest === i) break;
[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
i = smallest;
}
}
return top;
}
`
Peek — return \heap[0]\. O(1).
The naive analysis: "n inserts × O(log n) each = O(n log n)". Wrong. The smarter algorithm is bottom-up siftDown from the last non-leaf:
`js
function buildHeap(a) {
for (let i = (a.length >> 1) - 1; i >= 0; i--) siftDown(a, i);
}
`
Why it's O(n): nodes near the bottom (most of them) sift down very few levels.
| Level from bottom | Node count | Max sifts each |
| 0 (leaves) | n/2 | 0 |
| 1 | n/4 | 1 |
| 2 | n/8 | 2 |
| … | … | … |
Total work = \Σ (n/2^(k+1)) · k\ for k = 0..log n. That sum converges to n. So building a heap from an unsorted array is linear time. This is the reason heap sort starts with O(n) buildHeap, not O(n log n).
`js
function heapSort(a) {
buildHeap(a); // O(n) — max-heap variant
for (let end = a.length - 1; end > 0; end--) {
[a[0], a[end]] = [a[end], a[0]]; // move max to its final spot
siftDown(a, 0, end); // re-heapify [0..end)
}
}
`
Properties:
Dijkstra's shortest path — pull the closest unvisited node off a min-heap, relax edges. \O((V + E) log V)\ with a binary heap.
Huffman coding — repeatedly extract two minimum-frequency nodes, merge them, push back. Builds the optimal prefix code.
A\\* search — min-heap keyed on \g + h\.
OS scheduler / event simulation — min-heap of events keyed on next-fire-time.
Top-K — keep a min-heap of size K. For each new element: if it beats the heap min, replace + sift. After processing all n, the heap contains the K largest. O(n log K) instead of O(n log n) full sort.
K-way merge — push the head of each of K sorted lists into a min-heap. Pop, append to output, push that list's next element. O(n log K).
Median of a stream — two heaps:
`
max-heap (lower half) min-heap (upper half)
[3, 1, 2] ← median → [4, 6, 7]
`
Keep their sizes within 1 of each other. Median = root of the larger (or average of both roots if tied). O(log n) insert, O(1) median.
A d-ary heap has up to d children per node instead of 2.
| Binary heap | d-ary heap | ||||||
| Height | log₂ n | log_d n | |||||
| Sift-up | O(log₂ n) | O(log_d n) — faster | |||||
| Sift-down | O(log₂ n) | O(d · log_d n) — slower per level | Sift-up gets faster because the path is shorter. Sift-down gets slower because you compare against d children at each level. So d-ary heaps win whenever \ Advanced: Fibonacci HeapsTheoretical heavyweight. Lazy structure with merge-on-extract. | Op | Binary | Fibonacci (amortised) | |
| insert | O(log n) | O(1) | |||||
| find-min | O(1) | O(1) | |||||
| extract-min | O(log n) | O(log n) | |||||
| decrease-key | O(log n) | O(1) | |||||
| merge | O(n) | O(1) | Used in the textbook complexity proof of Dijkstra (\ Advanced: Standard Library Reality Check | Language | API | Default order | Workaround for the other |
| Java | \PriorityQueue | min | \new PriorityQueue<>(Collections.reverseOrder())\ | ||||
| Python | \heapq\ | min | push \-x\ and negate on pop | ||||
| C++ | \std::priority_queue\ | max | \std::priority_queue | ||||
| Rust | \BinaryHeap\ | max | wrap with \Reverse(x)\ | ||||
| Go | \container/heap\ | implement \Less\ yourself | flip the comparator | ||||
| JS / TS | none | — | hand-roll one or import a library |
The "Python is min, C++ is max" mismatch trips up nearly every cross-language interview. Always announce out loud which one you're using.
1. Implement \MinHeap\ from an array with \push\ (sift-up) and \pop\ (sift-down). Verify with a known sequence.
2. Solve Top K Frequent Elements with a size-K min-heap. Compare it to the O(n) bucket-sort solution.
3. Solve Merge K Sorted Lists in O(N log K) using a min-heap keyed on node value.
4. Implement a median-from-stream class using two heaps. Test that adding then querying after each element returns the correct median.