Lesson 21
Heaps & Priority Queues
Always know the smallest item — in O(1) — while inserting in O(log n).
01Why it matters & the intuition
Priority queues schedule OS processes, drive Dijkstra's shortest paths, merge k sorted streams and find top-k items. The binary heap is how they are built.
Think of it like…
A hospital emergency room: patients don't leave in arrival order but by severity. The most urgent is always at the front, and a new arrival is slotted in by comparing with just a few people — not the whole room.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
Same heap, as the array it really is
- comparing / current
- moving / removing
- done / found / visited
03Key ideas
Heap property
In a min-heap every parent ≤ its children, so the minimum is always the root. Siblings are unordered.
Stored in an array
A complete tree maps perfectly onto an array: children of i live at 2i + 1 and 2i + 2, parent at ⌊(i − 1) / 2⌋. No pointers needed.
Sift up / sift down
Insert at the end and swap upward while smaller than the parent. Extract the root by moving the last item to the top and swapping it down.
Heapify in O(n)
Building a heap from n items bottom-up takes O(n), not O(n log n) — most nodes are near the leaves and barely move.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
class MinHeap {
private a: number[] = [];
get size() { return this.a.length; }
peek(): number | undefined { return this.a[0]; }
push(x: number): void {
this.a.push(x);
let i = this.a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p] <= this.a[i]) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]];
i = p;
}
}
pop(): number | undefined {
if (!this.a.length) return undefined;
const top = this.a[0];
const last = this.a.pop()!;
if (this.a.length) {
this.a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < this.a.length && this.a[l] < this.a[m]) m = l;
if (r < this.a.length && this.a[r] < this.a[m]) m = r;
if (m === i) break;
[this.a[m], this.a[i]] = [this.a[i], this.a[m]];
i = m;
}
}
return top;
}
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Peek min | O(1) | — |
| Insert | O(log n) | — |
| Extract min | O(log n) | — |
| Build heap | O(n) | — |
| Heap sort | O(n log n) | O(1) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
K-th largest element
Write kth_largest(nums, k) returning the k-th largest value (1 = largest). Try it with a min-heap of size k — build one yourself or reason about a better approach than full sorting.