Priority Queue
A priority queue is an abstract data type where each element has an associated priority. Elements are served in order of their priority — not in the order they were inserted. Think of it as a queue where a VIP always jumps to the front.
Real-World Analogies
Hospital Triage — Patients are not treated in the order they arrive. A patient with a life-threatening condition is seen before someone with a minor injury, regardless of who walked in first. Each patient has a priority (severity score), and the doctor always treats the highest-priority patient next.
CPU Task Scheduling — An operating system uses a priority queue to decide which process runs next. High-priority system processes pre-empt low-priority user applications.
Dijkstra's Shortest Path — The algorithm always expands the unvisited node with the smallest tentative distance — a textbook min-heap use case.
Min-Heap vs Max-Heap
A binary heap is a complete binary tree stored as a flat array. There are two variants:
| Type | Rule | Root holds | |------|------|-----------| | Min-Heap | Every parent ≤ both children | The minimum element | | Max-Heap | Every parent ≥ both children | The maximum element |
Array Representation
A heap is stored in an array. For a node at index i:
- Left child → index
2i + 1 - Right child → index
2i + 2 - Parent → index
Math.floor((i - 1) / 2)
Min-Heap example — values [1, 3, 5, 7, 9, 8, 6]
1 ← index 0 (root / minimum)
/ \
3 5 ← index 1, 2
/ \ / \
7 9 8 6 ← index 3, 4, 5, 6
Array: [1, 3, 5, 7, 9, 8, 6]
The heap property is a local invariant: every node is smaller (min-heap) or larger (max-heap) than its direct children. There is no left-to-right ordering between siblings.
MinHeap — Full Implementation
The two core private helpers are heapifyUp (used after insert) and heapifyDown
(used after extract). Everything else is built on top of them.
class MinHeap {
constructor() {
this.heap = [];
}
// ── helpers ──────────────────────────────────────────────
_parent(i) { return Math.floor((i - 1) / 2); }
_left(i) { return 2 * i + 1; }
_right(i) { return 2 * i + 2; }
_swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// After inserting at the end, bubble the new node UP
// until the heap property is restored.
_heapifyUp(i) {
while (i > 0) {
const p = this._parent(i);
if (this.heap[p] > this.heap[i]) {
this._swap(p, i);
i = p;
} else {
break;
}
}
}
// After removing the root, the last element is placed at
// the root. Bubble it DOWN until the heap property is restored.
_heapifyDown(i) {
const n = this.heap.length;
while (true) {
let smallest = i;
const l = this._left(i);
const r = this._right(i);
if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
if (smallest !== i) {
this._swap(i, smallest);
i = smallest;
} else {
break;
}
}
}
// ── public API ───────────────────────────────────────────
/** Insert a value — O(log n) */
insert(val) {
this.heap.push(val);
this._heapifyUp(this.heap.length - 1);
}
/** Remove and return the minimum value — O(log n) */
extractMin() {
if (this.isEmpty()) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop(); // move last to root
this._heapifyDown(0);
return min;
}
/** Return the minimum without removing it — O(1) */
peek() {
return this.heap[0] ?? null;
}
size() { return this.heap.length; }
isEmpty() { return this.heap.length === 0; }
}
// ── Usage ────────────────────────────────────────────────
const h = new MinHeap();
[5, 3, 8, 1, 9, 2].forEach(v => h.insert(v));
console.log(h.peek()); // 1
console.log(h.extractMin()); // 1
console.log(h.extractMin()); // 2
console.log(h.extractMin()); // 3
console.log(h.size()); // 3
peek() → 1
extractMin() → 1
extractMin() → 2
extractMin() → 3
size() → 3
MaxHeap — Full Implementation
The max-heap is identical to the min-heap, with only the comparison operators flipped.
class MaxHeap {
constructor() {
this.heap = [];
}
_parent(i) { return Math.floor((i - 1) / 2); }
_left(i) { return 2 * i + 1; }
_right(i) { return 2 * i + 2; }
_swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
_heapifyUp(i) {
while (i > 0) {
const p = this._parent(i);
if (this.heap[p] < this.heap[i]) { // ← flipped
this._swap(p, i);
i = p;
} else {
break;
}
}
}
_heapifyDown(i) {
const n = this.heap.length;
while (true) {
let largest = i; // ← "largest" instead of "smallest"
const l = this._left(i);
const r = this._right(i);
if (l < n && this.heap[l] > this.heap[largest]) largest = l; // ← flipped
if (r < n && this.heap[r] > this.heap[largest]) largest = r; // ← flipped
if (largest !== i) {
this._swap(i, largest);
i = largest;
} else {
break;
}
}
}
/** Insert a value — O(log n) */
insert(val) {
this.heap.push(val);
this._heapifyUp(this.heap.length - 1);
}
/** Remove and return the maximum value — O(log n) */
extractMax() {
if (this.isEmpty()) return null;
if (this.heap.length === 1) return this.heap.pop();
const max = this.heap[0];
this.heap[0] = this.heap.pop();
this._heapifyDown(0);
return max;
}
peek() { return this.heap[0] ?? null; }
size() { return this.heap.length; }
isEmpty() { return this.heap.length === 0; }
}
// ── Usage ────────────────────────────────────────────────
const h = new MaxHeap();
[5, 3, 8, 1, 9, 2].forEach(v => h.insert(v));
console.log(h.peek()); // 9
console.log(h.extractMax()); // 9
console.log(h.extractMax()); // 8
console.log(h.extractMax()); // 5Time and Space Complexity
Operation | Binary Heap | Sorted Array | Unsorted Array | Notes |
|---|---|---|---|---|
insert | O(log n) | O(n) | O(1) | Heap bubbles up at most O(log n) levels |
extractMin / extractMax | O(log n) | O(1) | O(n) | Heap bubbles down at most O(log n) levels |
peek (min/max) | O(1) | O(1) | O(n) | Always at index 0 in a heap |
search arbitrary element | O(n) | O(log n) | O(n) | Heap has no BST ordering guarantee |
build heap from array | O(n) | O(n log n) | O(1) | Bottom-up heapify is linear |
heap sort | O(n log n) | — | — | n extractions × O(log n) each |
space | O(n) | O(n) | O(n) | Stored as a flat array — no pointer overhead |
Classic Problem 1 — K Largest Elements
Problem: Given an unsorted array, find the K largest elements.
Strategy: Maintain a min-heap of size K. Iterate through the array — if the current element is larger than the heap's minimum, evict the minimum and insert the new element. At the end, the heap contains exactly the K largest elements.
Why a min-heap? Because we want to quickly identify and discard the smallest element among our current top-K candidates.
function kLargest(nums, k) {
const heap = new MinHeap();
for (const num of nums) {
heap.insert(num);
if (heap.size() > k) {
heap.extractMin(); // discard the smallest so far
}
}
// Drain the heap — smallest first, so reverse for largest-first
const result = [];
while (!heap.isEmpty()) {
result.push(heap.extractMin());
}
return result.reverse();
}
console.log(kLargest([3, 1, 5, 12, 2, 11, 9, 7], 4));
// → [12, 11, 9, 7][12, 11, 9, 7]
Complexity: O(n log k) time — each of the n elements triggers at most one insert and one extract, both O(log k). Space is O(k) for the heap.
This beats sorting (O(n log n)) when k is much smaller than n.
Classic Problem 2 — Merge K Sorted Lists
Problem: Given K sorted linked lists, merge them into one sorted list.
Strategy: Use a min-heap that holds one node from each list. At each step, extract the global minimum, append it to the result, and push that node's successor (if any) into the heap.
// Assume ListNode = { val, next }
function mergeKSortedLists(lists) {
// Min-heap storing { val, node } — compare by val
class NodeHeap {
constructor() { this.data = []; }
_cmp(a, b) { return a.val - b.val; }
_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]]; }
insert(item) {
this.data.push(item);
let i = this.data.length - 1;
while (i > 0) {
const p = this._parent(i);
if (this._cmp(this.data[p], this.data[i]) > 0) {
this._swap(p, i); i = p;
} else break;
}
}
extractMin() {
if (!this.data.length) return null;
if (this.data.length === 1) return this.data.pop();
const min = this.data[0];
this.data[0] = this.data.pop();
let i = 0;
const n = this.data.length;
while (true) {
let s = i;
const l = this._left(i), r = this._right(i);
if (l < n && this._cmp(this.data[l], this.data[s]) < 0) s = l;
if (r < n && this._cmp(this.data[r], this.data[s]) < 0) s = r;
if (s !== i) { this._swap(i, s); i = s; } else break;
}
return min;
}
isEmpty() { return this.data.length === 0; }
}
const heap = new NodeHeap();
const dummy = { val: 0, next: null };
let tail = dummy;
// Seed the heap with the head of every list
for (const head of lists) {
if (head) heap.insert({ val: head.val, node: head });
}
while (!heap.isEmpty()) {
const { node } = heap.extractMin();
tail.next = node;
tail = tail.next;
if (node.next) heap.insert({ val: node.next.val, node: node.next });
}
return dummy.next;
}
// Example: merging three sorted lists
// [1 → 4 → 7], [2 → 5 → 8], [3 → 6 → 9]
// Result: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9Complexity: O(n log k) where n is the total number of nodes across all lists, and k is the number of lists. The heap never holds more than k elements.
Classic Problem 3 — Kth Largest Element
Problem: Find the Kth largest element in an unsorted array (LeetCode 215).
Two clean approaches:
Approach A — Min-Heap of size K (same pattern as K Largest):
// Approach A: min-heap, O(n log k)
function findKthLargest_heap(nums, k) {
const heap = new MinHeap();
for (const n of nums) {
heap.insert(n);
if (heap.size() > k) heap.extractMin();
}
return heap.peek(); // root is the Kth largest
}
// Approach B: QuickSelect, O(n) average, O(n²) worst
function findKthLargest_quickselect(nums, k) {
const target = nums.length - k; // Kth largest = target-th smallest (0-indexed)
function partition(lo, hi) {
const pivot = nums[hi];
let store = lo;
for (let i = lo; i < hi; i++) {
if (nums[i] <= pivot) {
[nums[store], nums[i]] = [nums[i], nums[store]];
store++;
}
}
[nums[store], nums[hi]] = [nums[hi], nums[store]];
return store;
}
function select(lo, hi) {
if (lo === hi) return nums[lo];
const p = partition(lo, hi);
if (p === target) return nums[p];
if (p < target) return select(p + 1, hi);
return select(lo, p - 1);
}
return select(0, nums.length - 1);
}
console.log(findKthLargest_heap([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest_quickselect([3, 2, 1, 5, 6, 4], 2)); // 5
heap approach: 5
quickselect approach: 5
Classic Problem 4 — Top K Frequent Elements
Problem: Given an array, return the K most frequent elements (LeetCode 347).
Strategy: Build a frequency map, then use a min-heap keyed by frequency. Keep only the top K frequencies in the heap.
function topKFrequent(nums, k) {
// Step 1: count frequencies
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
// Step 2: min-heap ordered by frequency — stores [frequency, value] pairs
class FreqHeap {
constructor() { this.data = []; }
_swap(i, j) { [this.data[i], this.data[j]] = [this.data[j], this.data[i]]; }
_parent(i) { return Math.floor((i - 1) / 2); }
_left(i) { return 2 * i + 1; }
_right(i) { return 2 * i + 2; }
insert(pair) {
this.data.push(pair);
let i = this.data.length - 1;
while (i > 0) {
const p = this._parent(i);
if (this.data[p][0] > this.data[i][0]) { this._swap(p, i); i = p; }
else break;
}
}
extractMin() {
if (this.data.length === 1) return this.data.pop();
const min = this.data[0];
this.data[0] = this.data.pop();
let i = 0, n = this.data.length;
while (true) {
let s = i;
const l = this._left(i), r = this._right(i);
if (l < n && this.data[l][0] < this.data[s][0]) s = l;
if (r < n && this.data[r][0] < this.data[s][0]) s = r;
if (s !== i) { this._swap(i, s); i = s; } else break;
}
return min;
}
size() { return this.data.length; }
}
const heap = new FreqHeap();
for (const [val, f] of freq) {
heap.insert([f, val]);
if (heap.size() > k) heap.extractMin(); // drop least-frequent
}
const result = [];
while (heap.size()) result.push(heap.extractMin()[1]);
return result;
}
console.log(topKFrequent([1,1,1,2,2,3], 2)); // [1, 2]
console.log(topKFrequent([1], 1)); // [1]
topKFrequent([1,1,1,2,2,3], 2) → [1, 2]
topKFrequent([1], 1) → [1]
Complexity: O(n log k) time. Building the frequency map is O(n); the heap never exceeds size k, so each insert/extract is O(log k).
Bonus — O(n) Bucket Sort approach: Create an array of n+1 buckets where index i holds all values with frequency i. Scan from right to left and collect the first k values.
Real-World Use Cases
Algorithm / System | Heap type | What it prioritises |
|---|---|---|
Dijkstra's shortest path | Min-heap | Node with smallest tentative distance |
Prim's MST | Min-heap | Edge with smallest weight |
A* search | Min-heap | Node with smallest f = g + h cost |
Huffman coding | Min-heap | Two trees with smallest frequency |
OS task scheduler | Max-heap | Process with highest priority level |
Event-driven simulation | Min-heap | Event with earliest timestamp |
Median of data stream | Min-heap + Max-heap | Maintain balanced halves |
K-way external merge sort | Min-heap | Smallest head across k sorted runs |
Dijkstra's Algorithm — Heap-Powered
The shortest-path algorithm is a direct application of a min-heap priority queue.
// graph: Map<node, Array<[neighbour, weight]>>
// This uses a MinHeap that compares [distance, node] pairs by distance.
function dijkstra(graph, start) {
const dist = new Map();
for (const node of graph.keys()) dist.set(node, Infinity);
dist.set(start, 0);
// We extend MinHeap to handle [dist, node] pairs
class DijkstraHeap {
constructor() { this.data = []; }
_swap(i, j) { [this.data[i], this.data[j]] = [this.data[j], this.data[i]]; }
_parent(i) { return Math.floor((i - 1) / 2); }
_left(i) { return 2 * i + 1; }
_right(i) { return 2 * i + 2; }
insert(pair) { // pair = [distance, node]
this.data.push(pair);
let i = this.data.length - 1;
while (i > 0) {
const p = this._parent(i);
if (this.data[p][0] > this.data[i][0]) { this._swap(p, i); i = p; }
else break;
}
}
extractMin() {
if (this.data.length === 1) return this.data.pop();
const min = this.data[0];
this.data[0] = this.data.pop();
let i = 0, n = this.data.length;
while (true) {
let s = i;
const l = this._left(i), r = this._right(i);
if (l < n && this.data[l][0] < this.data[s][0]) s = l;
if (r < n && this.data[r][0] < this.data[s][0]) s = r;
if (s !== i) { this._swap(i, s); i = s; } else break;
}
return min;
}
isEmpty() { return this.data.length === 0; }
}
const pq = new DijkstraHeap();
pq.insert([0, start]);
while (!pq.isEmpty()) {
const [d, u] = pq.extractMin();
// Skip stale entries (a shorter path was already found)
if (d > dist.get(u)) continue;
for (const [v, weight] of (graph.get(u) ?? [])) {
const newDist = dist.get(u) + weight;
if (newDist < dist.get(v)) {
dist.set(v, newDist);
pq.insert([newDist, v]);
}
}
}
return dist;
}
const graph = new Map([
['A', [['B', 1], ['C', 4]]],
['B', [['C', 2], ['D', 5]]],
['C', [['D', 1]]],
['D', []],
]);
const distances = dijkstra(graph, 'A');
// A→A: 0, A→B: 1, A→C: 3, A→D: 4
A → A : 0
A → B : 1
A → C : 3 (via B→C, not direct A→C which costs 4)
A → D : 4 (A→B→C→D = 1+2+1)
Median of a Data Stream
A classic two-heap trick: maintain a max-heap for the lower half and a min-heap for the upper half. The median is always at the tops of these two heaps.
- If total count is odd, the lower max-heap holds the extra element — its root is the median.
- If total count is even, the median is the average of both roots.
class MedianFinder {
constructor() {
this.lo = new MaxHeap(); // lower half — root is the largest of the lower half
this.hi = new MinHeap(); // upper half — root is the smallest of the upper half
}
addNum(num) {
// Always push to lo first
this.lo.insert(num);
// Balance: lo's max must be <= hi's min
if (!this.hi.isEmpty() && this.lo.peek() > this.hi.peek()) {
this.hi.insert(this.lo.extractMax());
}
// Keep sizes balanced: lo can be at most 1 larger than hi
if (this.lo.size() > this.hi.size() + 1) {
this.hi.insert(this.lo.extractMax());
} else if (this.hi.size() > this.lo.size()) {
this.lo.insert(this.hi.extractMin());
}
}
findMedian() {
if (this.lo.size() > this.hi.size()) return this.lo.peek();
return (this.lo.peek() + this.hi.peek()) / 2;
}
}
const mf = new MedianFinder();
mf.addNum(1); console.log(mf.findMedian()); // 1
mf.addNum(2); console.log(mf.findMedian()); // 1.5
mf.addNum(3); console.log(mf.findMedian()); // 2
mf.addNum(7); console.log(mf.findMedian()); // 2.5
After [1] → median: 1
After [1, 2] → median: 1.5
After [1, 2, 3] → median: 2
After [1, 2, 3, 7] → median: 2.5
Common Mistakes and How to Avoid Them
Forgetting to handle the single-element case in extractMin/extractMax — pop() alone is correct; do NOT also set heap[0] when the array has one element.
Off-by-one in parent/child index math — always double-check: parent = floor((i-1)/2), left = 2i+1, right = 2i+2.
Using a max-heap when a min-heap is needed for top-K problems — you want to evict the smallest element, so the root must be the minimum.
Not skipping stale heap entries in Dijkstra — always check if the extracted distance matches the recorded distance before processing neighbours.
Mutating heap array elements directly — always go through insert/extract so the heap invariant is maintained.
Assuming heap extraction always gives a globally sorted sequence — it does produce values in sorted order, but only because each extraction re-heapifies; the array itself is NOT sorted at any point.
Summary
Concept | Key point |
|---|---|
Priority Queue (ADT) | Elements dequeued by priority, not insertion order |
Min-Heap | Root is the minimum; parent <= children; used for find-min-fast |
Max-Heap | Root is the maximum; parent >= children; used for find-max-fast |
Array representation | parent = floor((i-1)/2), left = 2i+1, right = 2i+2 |
heapifyUp | Run after insert — swap with parent until heap property holds |
heapifyDown | Run after extract — swap with smaller/larger child until holds |
Build heap | O(n) bottom-up heapify — more efficient than n individual insertions |
Top-K pattern | Min-heap of size k — evict minimum when size exceeds k |
Dijkstra's algorithm | Min-heap on (distance, node) — always expand closest unvisited node |
Median stream | Max-heap (lo half) + Min-heap (hi half) — tops give the median |