Part 1 · Concepts · Heaps
Binary heap (priority queue)
Gives you the smallest item in O(1) and removes it in O(log n). A max heap is the same with the comparison flipped.
How it works
A complete binary tree stored in an array: the children of i are 2i+1 and 2i+2, and the parent is (i-1)/2. Rule: every parent is smaller than its children. Push: add at the end and swap upward while smaller than the parent. Pop: take the root, move the last item to the root, and swap downward with the smaller child. The tree is always balanced, so height is log n.
| peek min | O(1) |
| push / pop | O(log n) |
| build from n items | O(n) (heapify) |
| search for any item | O(n) |
Reach for it when
- Top k, k smallest, k most frequent
- Always process the cheapest or earliest next (Dijkstra, scheduling)
- Merge k sorted lists
- Running median (two heaps)
Implementation (JavaScript, tested)
class MinHeap {
cmp;
a = [];
constructor(cmp) {
this.cmp = cmp;
}
get size() {
return this.a.length;
}
peek() {
return this.a[0];
}
push(x) {
this.a.push(x);
let i = this.a.length - 1;
while (i > 0) {
// sift up: swap with parent while smaller
const p = (i - 1) >> 1;
if (this.cmp(this.a[i], this.a[p]) >= 0) break;
[this.a[i], this.a[p]] = [this.a[p], this.a[i]];
i = p;
}
}
pop() {
if (this.a.length === 0) return undefined;
const top = this.a[0],
last = this.a.pop();
if (this.a.length) {
this.a[0] = last;
let i = 0;
const n = this.a.length;
while (true) {
// sift down: swap with the smaller child
const l = 2 * i + 1,
r = l + 1;
let m = i;
if (l < n && this.cmp(this.a[l], this.a[m]) < 0) m = l;
if (r < n && this.cmp(this.a[r], this.a[m]) < 0) m = r;
if (m === i) break;
[this.a[i], this.a[m]] = [this.a[m], this.a[i]];
i = m;
}
}
return top;
}
}
// Max heap: new MinHeap((a, b) => b - a)Traps
- JS has no built-in heap. Be ready to write it, or say you'd use a library and write it if asked.
- For top k largest, keep a MIN heap of size k and pop when it grows past k. O(n log k).
- A heap is not sorted. Only the top is guaranteed.
In real systems: Node and libuv keep timers in a min heap (which setTimeout fires next). Job schedulers order delayed jobs the same way (BullMQ uses a Redis sorted set for delayed jobs).
Say out loud: I only need the next smallest each time, not a full sort, so a heap gives log n per operation.