Learn how complete binary heaps represent priority queues in array memory for O(log N) inserts and O(1) top priority retrieval.
Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.
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:
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)!