Heaps & Priority Queues

Think of it like this

Imagine an emergency room where patients aren't treated in arrival order — the most critically ill patient is always treated first. That's a priority queue: each element has a priority, and the highest-priority element is always at the front.

A heap is the data structure that implements a priority queue efficiently. It's a complete binary tree with one rule: the parent is always ≥ its children (max-heap) or always ≤ its children (min-heap).

Max-Heap:   90        Rule: parent ≥ both children
           /  \        Root = always the maximum
          75   82
         / \ / \
        55 60 71 45
 
Min-Heap:    5        Rule: parent ≤ both children
            /  \       Root = always the minimum
           12   8
          / \  / \
         20 15 10 11

The Array Trick

A complete binary tree can be stored perfectly in an array with no wasted space and no pointers. The index relationships are:

Array: [90, 75, 82, 55, 60, 71, 45]
Index:  0   1   2   3   4   5   6
 
For node at index i:
  parent     = Math.floor((i - 1) / 2)
  left child = 2 * i + 1
  right child= 2 * i + 2
 
Examples:
  Node 75 (i=1): parent = i=0 (90) ✓, left = i=3 (55), right = i=4 (60)
  Node 82 (i=2): parent = i=0 (90) ✓, left = i=5 (71), right = i=6 (45)

This is why heaps are cache-friendly and have no pointer overhead!

Time Complexity

Operation	Complexity	Why
Peek max/min	O(1)	Root is always `arr[0]`
Insert	O(log n)	Bubble up at most h = log n levels
Extract max/min	O(log n)	Bubble down at most h = log n levels
Build heap from array	O(n)	Not O(n log n) — see below
Heap sort	O(n log n)	n × extract
Search	O(n)	No order guarantee beyond parent/child

Space Complexity: O(n)

Core Operations — Heapify

class MaxHeap {
  constructor() { this.data = []; }
 
  // Helper to get parent/child indices
  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]]; }
 
  peek() { return this.data[0] ?? null; }
  size() { return this.data.length; }
 
  // Insert: add to end, bubble UP — O(log n)
  insert(val) {
    this.data.push(val);
    this._bubbleUp(this.data.length - 1);
  }
 
  _bubbleUp(i) {
    while (i > 0) {
      const p = this.parent(i);
      if (this.data[p] >= this.data[i]) break; // heap property satisfied
      this.swap(i, p);
      i = p;
    }
  }
 
  // Extract max: swap root with last, remove last, bubble DOWN — O(log n)
  extractMax() {
    if (this.data.length === 0) return null;
    if (this.data.length === 1) return this.data.pop();
 
    const max = this.data[0];
    this.data[0] = this.data.pop(); // move last to root
    this._bubbleDown(0);
    return max;
  }
 
  _bubbleDown(i) {
    const n = this.data.length;
    while (true) {
      let largest = i;
      const l = this.left(i), r = this.right(i);
      if (l < n && this.data[l] > this.data[largest]) largest = l;
      if (r < n && this.data[r] > this.data[largest]) largest = r;
      if (largest === i) break; // heap property satisfied
      this.swap(i, largest);
      i = largest;
    }
  }
 
  // Build heap from unsorted array — O(n) not O(n log n)!
  static fromArray(arr) {
    const h = new MaxHeap();
    h.data = [...arr];
    // Start from last internal node and heapify down
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
      h._bubbleDown(i);
    }
    return h;
  }
}

Why Build Heap is O(n), Not O(n log n)?

Intuition: Most nodes are near the bottom and barely need to bubble down. Leaves (half the nodes) need 0 swaps. Nodes one level up need at most 1 swap. The mathematical sum works out to O(n).

A 7-node heap:
 
Level 0 (root):  1 node,  height 2 → up to 2 swaps
Level 1:         2 nodes, height 1 → up to 1 swap each
Level 2 (leaves):4 nodes, height 0 → 0 swaps each
 
Total work = 1×2 + 2×1 + 4×0 = 4 = O(n) ✓

Visualized: Insert 95 into Max-Heap

Start:     90            Insert 95:     90
          /  \            append →    /  \  \
         75   82         at end      75  82  95
        / \                         / \
       55  60                      55  60
 
Bubble up: 95 > 82 → swap         90
                                  /  \
                                 75   95
                                / \ / \
                               55 60 82 (95 is now here)
 
95 > 90 → swap                   95
                                 /  \
                                75   90
                               / \ / \
                              55 60 82 (heap restored!)

Pattern 1 — Top K Elements (Min-Heap of Size K)

Keep a min-heap of size k. For each new element, if it's larger than the heap's root (the smallest of the top-k), swap it in. After processing all elements, the heap contains the k largest.

function topKLargest(nums, k) {
  const minHeap = new MinHeap(); // use a min-heap of size k
  for (const num of nums) {
    minHeap.insert(num);
    if (minHeap.size() > k) minHeap.extractMin(); // evict smallest
  }
  return minHeap.toArray(); // k largest elements
}
 
// Example: nums=[3,1,5,12,2,11], k=3
// After 3: heap=[3]
// After 1: heap=[1,3]
// After 5: heap=[1,3,5]
// After 12: size=4>3 → evict min(1): heap=[3,5,12]
// After 2: size=4>3 → evict min(2): heap=[3,5,12]   (2<3, evicted immediately)
// After 11: size=4>3 → evict min(3): heap=[5,11,12]
// Result: [5,11,12] ✓

Pattern 2 — Median of Data Stream (Two Heaps)

Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half. The median sits at the boundary.

class MedianFinder {
  #lower = new MaxHeap(); // left half, max-heap
  #upper = new MinHeap(); // right half, min-heap
 
  addNum(num) {
    // Step 1: Route to correct half
    if (!this.#lower.size() || num <= this.#lower.peek()) {
      this.#lower.insert(num);
    } else {
      this.#upper.insert(num);
    }
    // Step 2: Rebalance so sizes differ by at most 1
    if (this.#lower.size() > this.#upper.size() + 1) {
      this.#upper.insert(this.#lower.extractMax());
    } else if (this.#upper.size() > this.#lower.size()) {
      this.#lower.insert(this.#upper.extractMin());
    }
  }
 
  findMedian() {
    if (this.#lower.size() === this.#upper.size()) {
      return (this.#lower.peek() + this.#upper.peek()) / 2;
    }
    return this.#lower.peek(); // lower has one extra
  }
}

Real-World Frontend Application

React Concurrent Mode Scheduler: Internally uses a min-heap to schedule tasks by priority (expiration time). User interactions get the smallest expiration (highest priority) and jump to the front
Dijkstra's algorithm: Used by Google Maps, Mapbox, and any shortest-path routing — always expands the cheapest unvisited node using a min-heap
Video streaming buffering: Priority queues decide which video segments to fetch next when bandwidth is limited
Browser task scheduling: The job queue and microtask queue effectively implement priority between synchronous, microtask, and macrotask work

Common Mistakes

Mistake	What Happens	Fix
Using max-heap when you need min-heap	"Top K largest" returns K smallest	For min-heap: negate values in max-heap, or implement MinHeap
Forgetting to heapify after bulk insert	Heap property violated	Call `buildHeap` / `fromArray` instead of inserting one by one
Off-by-one in parent/child formulas	Wrong node relationships	Parent: `(i-1)/2`. Left: `2i+1`. Right: `2i+2`.
Confusing heap with sorted array	Heap root = min/max, but the rest is NOT sorted	Heap only guarantees the root, not full order

Key Problems to Solve

#	Problem	Pattern	Difficulty
1	Kth Largest Element in Array	Min-heap of size k	Medium
2	Top K Frequent Elements	Max-heap or bucket sort	Medium
3	Find Median from Data Stream	Two heaps (max + min)	Hard
4	Merge K Sorted Lists	Min-heap on list heads	Hard
5	Task Scheduler	Max-heap + idle time	Medium
6	Reorganize String	Max-heap of frequencies	Medium
7	K Closest Points to Origin	Max-heap of size k	Medium
8	Smallest Range Covering K Lists	Min-heap + global max tracking	Hard
9	Heap Sort	Build heap + n × extractMax	Medium
10	Network Delay Time	Dijkstra with min-heap	Medium

Max-Heap: 90 Rule: parent ≥ both children / \ Root = always the maximum 75 82 / \ / \ 55 60 71 45 Min-Heap: 5 Rule: parent ≤ both children / \ Root = always the minimum 12 8 / \ / \ 20 15 10 11

Array: [90, 75, 82, 55, 60, 71, 45] Index: 0 1 2 3 4 5 6 For node at index i: parent = Math.floor((i - 1) / 2) left child = 2 * i + 1 right child= 2 * i + 2 Examples: Node 75 (i=1): parent = i=0 (90) ✓, left = i=3 (55), right = i=4 (60) Node 82 (i=2): parent = i=0 (90) ✓, left = i=5 (71), right = i=6 (45)

Operation

Complexity

Why

Peek max/min

O(1)

Root is always arr[0]

Insert

O(log n)

Bubble up at most h = log n levels

Extract max/min

O(log n)

Bubble down at most h = log n levels

Build heap from array

O(n)

Not O(n log n) — see below

Heap sort

O(n log n)

n × extract

O(n)

No order guarantee beyond parent/child

class MaxHeap { constructor() { this.data = []; } // Helper to get parent/child indices 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]]; } peek() { return this.data[0] ?? null; } size() { return this.data.length; } // Insert: add to end, bubble UP — O(log n) insert(val) { this.data.push(val); this._bubbleUp(this.data.length - 1); } _bubbleUp(i) { while (i > 0) { const p = this.parent(i); if (this.data[p] >= this.data[i]) break; // heap property satisfied this.swap(i, p); i = p; } } // Extract max: swap root with last, remove last, bubble DOWN — O(log n) extractMax() { if (this.data.length === 0) return null; if (this.data.length === 1) return this.data.pop(); const max = this.data[0]; this.data[0] = this.data.pop(); // move last to root this._bubbleDown(0); return max; } _bubbleDown(i) { const n = this.data.length; while (true) { let largest = i; const l = this.left(i), r = this.right(i); if (l < n && this.data[l] > this.data[largest]) largest = l; if (r < n && this.data[r] > this.data[largest]) largest = r; if (largest === i) break; // heap property satisfied this.swap(i, largest); i = largest; } } // Build heap from unsorted array — O(n) not O(n log n)! static fromArray(arr) { const h = new MaxHeap(); h.data = [...arr]; // Start from last internal node and heapify down for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) { h._bubbleDown(i); } return h; } }

A 7-node heap: Level 0 (root): 1 node, height 2 → up to 2 swaps Level 1: 2 nodes, height 1 → up to 1 swap each Level 2 (leaves):4 nodes, height 0 → 0 swaps each Total work = 1×2 + 2×1 + 4×0 = 4 = O(n) ✓

Start: 90 Insert 95: 90 / \ append → / \ \ 75 82 at end 75 82 95 / \ / \ 55 60 55 60 Bubble up: 95 > 82 → swap 90 / \ 75 95 / \ / \ 55 60 82 (95 is now here) 95 > 90 → swap 95 / \ 75 90 / \ / \ 55 60 82 (heap restored!)

function topKLargest(nums, k) { const minHeap = new MinHeap(); // use a min-heap of size k for (const num of nums) { minHeap.insert(num); if (minHeap.size() > k) minHeap.extractMin(); // evict smallest } return minHeap.toArray(); // k largest elements } // Example: nums=[3,1,5,12,2,11], k=3 // After 3: heap=[3] // After 1: heap=[1,3] // After 5: heap=[1,3,5] // After 12: size=4>3 → evict min(1): heap=[3,5,12] // After 2: size=4>3 → evict min(2): heap=[3,5,12] (2<3, evicted immediately) // After 11: size=4>3 → evict min(3): heap=[5,11,12] // Result: [5,11,12] ✓

class MedianFinder { #lower = new MaxHeap(); // left half, max-heap #upper = new MinHeap(); // right half, min-heap addNum(num) { // Step 1: Route to correct half if (!this.#lower.size() || num <= this.#lower.peek()) { this.#lower.insert(num); } else { this.#upper.insert(num); } // Step 2: Rebalance so sizes differ by at most 1 if (this.#lower.size() > this.#upper.size() + 1) { this.#upper.insert(this.#lower.extractMax()); } else if (this.#upper.size() > this.#lower.size()) { this.#lower.insert(this.#upper.extractMin()); } } findMedian() { if (this.#lower.size() === this.#upper.size()) { return (this.#lower.peek() + this.#upper.peek()) / 2; } return this.#lower.peek(); // lower has one extra } }

Mistake

What Happens

Fix

Using max-heap when you need min-heap

"Top K largest" returns K smallest

For min-heap: negate values in max-heap, or implement MinHeap

Forgetting to heapify after bulk insert

Heap property violated

Call buildHeap / fromArray instead of inserting one by one

Off-by-one in parent/child formulas

Wrong node relationships

Parent: (i-1)/2. Left: 2i+1. Right: 2i+2.

Confusing heap with sorted array

Heap root = min/max, but the rest is NOT sorted

Heap only guarantees the root, not full order

Problem

Pattern

Difficulty

Kth Largest Element in Array

Min-heap of size k

Medium

Top K Frequent Elements

Max-heap or bucket sort

Medium

Find Median from Data Stream

Two heaps (max + min)

Hard

Merge K Sorted Lists

Min-heap on list heads

Hard

Task Scheduler

Max-heap + idle time

Medium

Reorganize String

Max-heap of frequencies

Medium

K Closest Points to Origin

Max-heap of size k

Medium

Smallest Range Covering K Lists

Min-heap + global max tracking

Hard

Heap Sort

Build heap + n × extractMax

Medium

Network Delay Time

Dijkstra with min-heap

Medium

Heaps & Priority Queues