Heaps & Priority Queues

0/12 in this phase0/57 across the roadmap

📖 Concept

A heap is a complete binary tree that satisfies the heap property:

Max-Heap: Every parent ≥ its children (root is maximum)
Min-Heap: Every parent ≤ its children (root is minimum)

Stored as an array (not a tree with nodes/pointers):

Parent of i: Math.floor((i - 1) / 2)
Left child of i: 2 * i + 1
Right child of i: 2 * i + 2

Operations:

Operation	Complexity
Insert (push)	O(log n) — add at end, bubble up
Extract max/min (pop)	O(log n) — swap root with last, bubble down
Peek (get max/min)	O(1)
Build heap from array	O(n) — NOT O(n log n)

Priority Queue is the abstract concept; Heap is the implementation.

Key interview patterns:

Top K elements — Use min-heap of size k
Kth largest — Min-heap of size k, root is answer
Merge K sorted lists — Min-heap of k current elements
Median from stream — Two heaps: max-heap for lower half, min-heap for upper half
Task scheduler — Max-heap for frequency counting

🏠 Real-world analogy: A hospital ER. The min-heap is the triage list — the most critical patient (smallest severity number) is always treated first, regardless of arrival order.

💻 Code Example

codeTap to expand ⛶

1// MIN-HEAP — Full Implementation
2class MinHeap {
3  constructor() { this.heap = []; }
4
5  push(val) {
6    this.heap.push(val);
7    this._bubbleUp(this.heap.length - 1);
8  }
9
10  pop() {
11    if (this.heap.length === 0) return undefined;
12    const top = this.heap[0];
13    const last = this.heap.pop();
14    if (this.heap.length > 0) {
15      this.heap[0] = last;
16      this._bubbleDown(0);
17    }
18    return top;
19  }
20
21  peek() { return this.heap[0]; }
22  size() { return this.heap.length; }
23
24  _bubbleUp(i) {
25    while (i > 0) {
26      const parent = Math.floor((i - 1) / 2);
27      if (this.heap[parent] <= this.heap[i]) break;
28      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
29      i = parent;
30    }
31  }
32
33  _bubbleDown(i) {
34    const n = this.heap.length;
35    while (true) {
36      let smallest = i;
37      const left = 2 * i + 1, right = 2 * i + 2;
38      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
39      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
40      if (smallest === i) break;
41      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
42      i = smallest;
43    }
44  }
45}
46
47// TOP K FREQUENT ELEMENTS
48function topKFrequent(nums, k) {
49  const freq = new Map();
50  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
51
52  // Bucket sort approach — O(n)
53  const buckets = new Array(nums.length + 1).fill(null).map(() => []);
54  for (const [num, count] of freq) buckets[count].push(num);
55
56  const result = [];
57  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
58    result.push(...buckets[i]);
59  }
60  return result.slice(0, k);
61}
62
63// KTH LARGEST — Min-heap of size k
64function findKthLargest(nums, k) {
65  const heap = new MinHeap();
66  for (const n of nums) {
67    heap.push(n);
68    if (heap.size() > k) heap.pop(); // Remove smallest
69  }
70  return heap.peek(); // Kth largest!
71}
72
73// MERGE K SORTED LISTS — Min-heap
74function mergeKLists(lists) {
75  const heap = new MinHeap(); // Would need custom comparator
76  for (let i = 0; i < lists.length; i++) {
77    if (lists[i]) heap.push({ val: lists[i].val, node: lists[i], listIdx: i });
78  }
79  const dummy = { next: null };
80  let curr = dummy;
81  while (heap.size() > 0) {
82    const { node } = heap.pop();
83    curr.next = node;
84    curr = curr.next;
85    if (node.next) heap.push({ val: node.next.val, node: node.next });
86  }
87  return dummy.next;
88}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

Implement a min-heap from scratch with push, pop, peek
Find the kth largest element in an array
Top K frequent elements
Merge K sorted linked lists
Sort a nearly sorted array (k-sorted)
Find median from data stream (two heaps)
Reorganize string so no two adjacent characters are the same
Task scheduler — minimum time to complete tasks with cooldown
Kth smallest element in a sorted matrix
Sliding window median

⚠️ Common Mistakes

Confusing min-heap and max-heap — for top-K largest use min-heap (counterintuitive!)
Not using the array formula correctly — parent = (i-1)/2, children = 2i+1, 2i+2
Building heap by inserting one-by-one O(n log n) vs heapify O(n) — heapify is faster
JavaScript has no built-in heap — you must implement one or use a library
Confusing heap with BST — heap is NOT sorted, only parent-child ordering is guaranteed

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Heaps & Priority Queues

Was this topic helpful?

← PreviousBinary Search Trees (BST) — Build, Search, Balance Next →Graphs — Representations & Fundamentals