Chapter 16 — Heaps & Priority Queues
Chapter 16 — Heaps & Priority Queues
Hey everyone! Welcome back to Namaste DSA!
A heap is a special tree that always keeps the smallest (or largest) element at the top, ready to grab in O(1). It powers priority queues, Dijkstra's shortest path, and the famous "top K elements" problems. The clever part: a heap secretly lives inside a plain array.
What we will cover:
- Min-heap vs Max-heap
- How a heap lives inside an array
- Bubble up / bubble down (push & pop)
- The "Top K elements" pattern
- Heap Sort
- Interview Questions
1. Min-Heap vs Max-Heap
┌─────────────────────────────────────────────────────────────┐ │ HEAP PROPERTY (a "complete" binary tree) │ ├─────────────────────────────────────────────────────────────┤ │ │ │ MIN-HEAP: every parent ≤ its children │ │ → smallest value at the ROOT │ │ │ │ (1) ← min is always on top │ │ / \ │ │ (3) (6) │ │ / \ │ │ (5) (9) │ │ │ │ MAX-HEAP: every parent ≥ its children → largest on top │ └─────────────────────────────────────────────────────────────┘
Note: a heap is NOT sorted — it only guarantees the top. The rest is loosely ordered, which is exactly why it's cheaper to maintain than a fully sorted structure.
2. A Heap Lives in an Array
Because a heap is a complete tree (filled left to right), we can store it in an array with no pointers. Simple index math links parents and children:
Tree: (1) Array: [1, 3, 6, 5, 9]
/ \ index: 0 1 2 3 4
(3) (6)
/ \
(5) (9)
For index i:
parent = (i - 1) / 2 (floor)
left child = 2i + 1
right child = 2i + 2
Example: node at index 1 (value 3)
children at 3 (=5) and 4 (=9) ✔
3. Push (Bubble Up) & Pop (Bubble Down)
PUSH: add at the end, then BUBBLE UP while smaller than parent. POP: remove root, move last element to root, BUBBLE DOWN. Both are O(log n) — the height of the tree.
class MinHeap {
constructor() { this.h = []; }
push(val) {
this.h.push(val);
let i = this.h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1; // parent index
if (this.h[p] <= this.h[i]) break; // heap ok
[this.h[p], this.h[i]] = [this.h[i], this.h[p]];
i = p; // bubble up
}
}
pop() {
const top = this.h[0];
const last = this.h.pop();
if (this.h.length) {
this.h[0] = last;
let i = 0, n = this.h.length;
while (true) {
let smallest = i, l = 2*i+1, r = 2*i+2;
if (l < n && this.h[l] < this.h[smallest]) smallest = l;
if (r < n && this.h[r] < this.h[smallest]) smallest = r;
if (smallest === i) break;
[this.h[i], this.h[smallest]] = [this.h[smallest], this.h[i]];
i = smallest; // bubble down
}
}
return top;
}
peek() { return this.h[0]; }
get size() { return this.h.length; }
}
| Operation | Time |
|---|---|
| peek (top) | O(1) |
| push | O(log n) |
| pop | O(log n) |
| build heap from array | O(n) |
4. The "Top K Elements" Pattern
Find the K largest elements. Keeping a min-heap of size K does it in O(n log k) — far better than sorting everything (O(n log n)) when k is small.
function topK(nums, k) {
const heap = new MinHeap();
for (const n of nums) {
heap.push(n);
if (heap.size > k) heap.pop(); // drop the smallest → keep top K
}
return heap.h; // the K largest
}
WHY a MIN-heap for the K LARGEST? The heap holds the K biggest seen so far. Its smallest (the root) is the "weakest survivor." A new number bigger than the root kicks the root out.
5. Heap Sort
Build a max-heap, then repeatedly pop the max to the end. O(n log n) time, O(1) extra space — but unstable.
function heapSort(arr) {
const heap = new MinHeap();
for (const x of arr) heap.push(x);
const res = [];
while (heap.size) res.push(heap.pop()); // pops in ascending order
return res;
}
Interview Questions — Quick Fire!
Q: What is a heap and how is it different from a BST?
"A heap is a complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children, so the extreme element is always at the root. Unlike a BST it isn't fully sorted — there's no left/right ordering — it only guarantees the top, which makes push and pop O(log n)."
Q: How is a heap stored in an array?
"Because it's a complete tree, you store it level by level in an array. For index i, the parent is at (i-1)/2, the left child at 2i+1, and the right child at 2i+2. No pointers needed."
Q: How do push and pop keep the heap valid?
"Push adds the element at the end and bubbles it up by swapping with its parent while it violates the heap property. Pop removes the root, moves the last element to the top, and bubbles it down by swapping with its smaller child. Both are O(log n)."
Q: For the K largest elements, why use a min-heap of size K?
"The heap holds the K largest seen so far, and its root is the smallest of those. When a new element is bigger than the root, it replaces it; otherwise it's discarded. Keeping only K elements makes it O(n log k), better than sorting everything when k is small."
Q: What's a real use of a priority queue?
"Dijkstra's shortest-path algorithm uses one to always expand the closest unvisited node next. Other uses include task scheduling by priority, merging k sorted lists, and event simulation."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Min/Max heap | Extreme element always at the root. |
| Array storage | parent (i-1)/2, children 2i+1, 2i+2. |
| push/pop | Bubble up / down — O(log n). |
| peek | O(1). |
| Top K | Size-K min-heap → O(n log k). |
What's Next?
Chapter 17: Tries — a tree built from letters that makes prefix search and autocomplete lightning fast.
Keep coding, keep grinding! See you in the next one!
Post a Comment