Heaps & Priority Queues
Think of it like this
Imagine an emergency room where patients aren't treated in arrival order, the most critically ill patient is always treated first. That's a priority queue: each element has a priority, and the highest-priority element is always at the front.
A heap is the data structure that implements a priority queue efficiently. It's a complete binary tree with one rule: the parent is always ≥ its children (max-heap) or always ≤ its children (min-heap).
Max-Heap: 90 Rule: parent ≥ both children
/ \ Root = always the maximum
75 82
/ \ / \
55 60 71 45
Min-Heap: 5 Rule: parent ≤ both children
/ \ Root = always the minimum
12 8
/ \ / \
20 15 10 11The Array Trick
A complete binary tree can be stored perfectly in an array with no wasted space and no pointers. The index relationships are:
Array: [90, 75, 82, 55, 60, 71, 45]
Index: 0 1 2 3 4 5 6
For node at index i:
parent = Math.floor((i - 1) / 2)
left child = 2 * i + 1
right child= 2 * i + 2
Examples:
Node 75 (i=1): parent = i=0 (90) ✓, left = i=3 (55), right = i=4 (60)
Node 82 (i=2): parent = i=0 (90) ✓, left = i=5 (71), right = i=6 (45)This is why heaps are cache-friendly and have no pointer overhead!
Time Complexity
| Operation | Complexity | Why |
|---|---|---|
| Peek max/min | O(1) | Root is always arr[0] |
| Insert | O(log n) | Bubble up at most h = log n levels |
| Extract max/min | O(log n) | Bubble down at most h = log n levels |
| Build heap from array | O(n) |
Space Complexity: O(n)
Core Operations, Heapify
class MaxHeap {
constructor() { this.data = []; }
// Helper to get parent/child indices
parent(i) { return Math.floor((i - 1) / 2); }
left(i) { return 2 * i + 1; }
right(i) { return 2 * i + 2; }
swap(i, j) { [this.data[i], this.data[j]] = [this.data[j], this.data[i]]; }