Heaps and Priority Queues Deep Dive
Master binary heaps, heap operations, priority queues, and heap-sort.
What you'll learn
- Binary heap properties and array representation
- Heap operations: insert, extract, heapify
- Priority queue applications
- Heap-sort and its O(n log n) guarantee
Concept
Heaps and Priority Queues Deep Dive
A heap is a complete binary tree where each parent is <= (min-heap) or >= (max-heap) its children. The heap property ensures the minimum (or maximum) is always at the root, accessible in O(1).
Array Representation
A complete binary tree can be stored in an array without pointers: the children of index i are at 2i+1 and 2i+2, and the parent of i is at (i-1)/2 (integer division). This is cache-friendly (contiguous memory) and avoids pointer overhead.
Core Operations
insert (O(log n)): add at the end, then bubble up - swap with parent while heap property is violated. extractMin/Max (O(log n)): take the root, move the last element to the root, then sift down. heapify (O(n)): build a heap from an unordered array by sifting down from the middle index to 0.
Priority Queue
A priority queue is an abstract data type where each element has a priority; dequeue returns the highest-priority element. Heaps are the standard implementation. Applications: Dijkstra algorithm (extract-closest), Huffman coding (merge two least-frequent), event-driven simulation, task scheduling.
Heap-Sort
Heap-sort builds a heap in O(n), then repeatedly extracts the max into the back of the array. It is O(n log n) worst-case, in-place (O(1) extra space), but not stable. It is the only common sort that is both O(n log n) worst-case and in-place.
Example
class PriorityQueue {
constructor(compare = (a, b) => a < b) { this.h = []; this.compare = compare; }
push(x) {
this.h.push(x); let i = this.h.length - 1;
while (i > 0) { const p = (i - 1) >> 1; if (!this.compare(this.h[i], this.h[p])) break; [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
}
pop() {
const top = this.h[0]; const last = this.h.pop();
if (this.h.length > 0) {
this.h[0] = last; let i = 0, n = this.h.length;
while (true) { let s = i, l = 2*i+1, r = 2*i+2; if (l < n && this.compare(this.h[l], this.h[s])) s = l; if (r < n && this.compare(this.h[r], this.h[s])) s = r; if (s === i) break; [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s; }
}
return top;
}
get size() { return this.h.length; }
}
const pq = new PriorityQueue((a, b) => a.priority < b.priority);
pq.push({task: 'render', priority: 1}); pq.push({task: 'fetch', priority: 3}); pq.push({task: 'log', priority: 2});
while (pq.size) console.log(pq.pop().task);
The priority queue uses a comparison function to determine ordering. push bubbles up, pop sifts down. The task scheduler processes highest-priority tasks first.
Try it
- Crontab Generator
Scheduled jobs often use priority queues - see how priority affects execution order.
Common mistakes
The mistake
Using a sorted array instead of a heap for a priority queue.
The fix
A sorted array gives O(n) insert. A heap gives O(log n) insert and extract - use it for dynamic priority queues.
The mistake
Confusing min-heap and max-heap.
The fix
A min-heap root is the minimum; a max-heap root is the maximum. Be consistent - mixing them produces wrong results.
Look up unfamiliar terms
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.