Heaps & Priority Queues (Min-Heap / Max-Heap)
Quick Overview
A heap only guarantees each parent beats its children, never a full ordering. That weaker promise is exactly what makes the top element `O(1)` to read and `O(log N)` to replace.
Deep Dive
1. Priority-Based Retrieval
A Priority Queue is an abstract data structure where elements have priorities. A Heap is an efficient array-based implementation of a priority queue:
- Min-Heap: The root node is always the minimum element.
- Max-Heap: The root node is always the maximum element.
2. Array Representation of Heaps
A heap is a Complete Binary Tree stored contiguously in an array without pointer overhead:
- For node at index
i:Parent(i) = Math.floor((i - 1) / 2)LeftChild(i) = 2 * i + 1RightChild(i) = 2 * i + 2
Tree View: Array View:
[ 1 ] Index: [ 0 | 1 | 2 | 3 | 4 ]
/ \ Value: [ 1 | 3 | 2 | 7 | 5 ]
[ 3 ] [ 2 ]
/ \
[ 7 ] [ 5 ]
3. Min-Heap Operations Implementation
class MinHeap {
constructor() {
this.data = [];
}
insert(val) {
this.data.push(val);
this.bubbleUp(this.data.length - 1); // Restore heap property up
}
extractMin() {
if (this.data.length === 0) return null;
if (this.data.length === 1) return this.data.pop();
const min = this.data[0];
this.data[0] = this.data.pop(); // Move last element to root
this.bubbleDown(0); // Restore heap property down
return min;
}
bubbleUp(index) {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (this.data[index] >= this.data[parent]) break;
[this.data[index], this.data[parent]] = [this.data[parent], this.data[index]];
index = parent;
}
}
bubbleDown(index) {
const len = this.data.length;
while (2 * index + 1 < len) {
let smallest = 2 * index + 1;
const right = smallest + 1;
if (right < len && this.data[right] < this.data[smallest]) {
smallest = right;
}
if (this.data[index] <= this.data[smallest]) break;
[this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
index = smallest;
}
}
}
4. Top K Frequent Elements Pattern
Instead of sorting all N items in O(N log N), maintain a Min-Heap of size K to find top K elements in O(N log K) time!
5. Common Mistakes
- Assuming Heaps are Fully Sorted: A heap only guarantees that parent nodes are smaller/larger than children. Array indices are NOT fully sorted!
6. Next Steps
Use heaps for streaming medians and Dijkstra's algorithm. Next, let's explore Tries (Prefix Trees)!
Next Up in Data Structures & Algorithms Core Patterns
Big O Notation: Time & Space Complexity
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
Dynamic Arrays & Amortized Resizing
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
Two Pointers Pattern (Converging & Symmetrical)
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.