🏔️ Heap (Priority Queue)

One-line summary: A complete binary tree satisfying the heap property — O(log n) insert and extract-min/max, the engine behind Top-K, median, K-way merge, and scheduling algorithms.

---

Diagram

Concept

• Min-heap: parent ≤ children → peek() is minimum.
• Max-heap: parent ≥ children → peek() is maximum.
• JavaScript has no native heap — simulate with sorted array or use @datastructures-js/priority-queue.

Key operations: insert O(log n), extractMin/Max O(log n), peek O(1), heapify O(n).

---

Time & Space Complexity

Operation	Time	Space
Insert	O(log n)	O(1)
Extract min/max	O(log n)	O(1)
Peek	O(1)	O(1)
Heapify	O(n)	O(1)
Top-K elements	O(n log k)	O(k)
K-way merge (n total, k lists)	O(n log k)	O(k)

---

Common Patterns

Pattern 1 — Top-K Frequent (Min-Heap of size K)

function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Pattern 2 — Two Heaps (Median from Stream)

// maxHeap = lower half, minHeap = upper half
// Invariant: |maxHeap.size - minHeap.size| <= 1
// Median = maxHeap.top() or avg of both tops

Pattern 3 — K-way Merge

// 1. Add first element from each list to min-heap with [value, listIdx, elemIdx]
// 2. Extract min → push to result → add next element from same list
// 3. Repeat until heap empty

---

Pitfalls

• JS has no native heap — off-the-shelf sort trick is O(n log n), not O(n log k)
• Rebalancing Two Heaps: ensure size diff ≤ 1 after every insert
• K-way merge: track which list each heap element came from

---

Practice Problems

Problem	Difficulty	Solution
LC 215 — Kth Largest Element	Medium	View Solution
LC 973 — K Closest Points to Origin	Medium
LC 295 — Find Median from Data Stream	Hard
LC 23 — Merge K Sorted Lists	Hard
LC 378 — Kth Smallest in Sorted Matrix	Medium
LC 373 — Find K Pairs with Smallest Sums	Medium
LC 480 — Sliding Window Median	Hard
LC 502 — IPO	Hard
LC 703 — Kth Largest Element in a Stream	Easy
CC — IPC Trainers (IPCTRAIN)	Hard
LC 1046 — Last Stone Weight	Easy
LC 1337 — The K Weakest Rows in a Matrix	Easy
LC 1464 — Maximum Product of Two Elements in an Array	Easy
LC 1845 — Seat Reservation Manager	Medium
LC 347 — Top K Frequent Elements	Medium
LC 692 — Top K Frequent Words	Medium
LC 1167 — Minimum Cost to Connect Sticks	Medium
LC 1353 — Maximum Number of Events That Can Be Attended	Medium
LC 1642 — Furthest Building You Can Reach	Medium
LC 1834 — Single-Threaded CPU	Medium
LC 2542 — Maximum Subsequence Score	Medium
CC — Heap Operations (HEAPOPS)	Medium
CC — Priority Queue (PRIORQUE)	Medium
LC 218 — The Skyline Problem	Hard
LC 239 — Sliding Window Maximum	Hard
LC 407 — Trapping Rain Water II	Hard
LC 632 — Smallest Range Covering Elements from K Lists	Hard
LC 857 — Minimum Cost to Hire K Workers	Hard
LC 1439 — Find the Kth Smallest Sum of a Matrix With Sorted Rows	Hard
LC 2386 — Find the K-Sum of an Array	Hard
CC — Advanced Heap (ADVHEAP)	Hard

---

Related Topics

• Trees — heap is a complete binary tree
• Sorting — heapsort uses heap operations
• Graphs — Dijkstra uses min-heap

← Back to Home · © sparshjaswal