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.
A Priority Queue is an abstract data structure where elements have priorities. A Heap is an efficient array-based implementation of a priority queue:
A heap is a Complete Binary Tree stored contiguously in an array without pointer overhead:
i:
Parent(i) = Math.floor((i - 1) / 2)LeftChild(i) = 2 * i + 1RightChild(i) = 2 * i + 2Tree View: Array View:
[ 1 ] Index: [ 0 | 1 | 2 | 3 | 4 ]
/ \ Value: [ 1 | 3 | 2 | 7 | 5 ]
[ 3 ] [ 2 ]
/ \
[ 7 ] [ 5 ]
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;
}
}
}
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!
Use heaps for streaming medians and Dijkstra's algorithm. Next, let's explore Tries (Prefix Trees)!
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.
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.
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.