Blind 75 — Heap (Priority Queue) Pattern Guide

How to Identify a “Heap” Problem

Interview Triggers

• “Find the K-th largest / smallest / most frequent”
• “Top K elements” / “K closest points”
• “Merge K sorted …”
• “Running median of a stream”
• “Schedule / next task” with priority
• You repeatedly need the min or max of a changing collection

Which Sub-Pattern Does It Belong To?

If the prompt says…	Use this sub-pattern	Example LC
Merge K sorted lists / streams	Min-heap of heads	23
Top-K most frequent elements	Min-heap of size K OR bucket sort	347
Streaming median	Two heaps (max-low, min-high)	295

---

The Decision Tree

HEAP PROBLEM
│
├─ "Find K-th X / Top K X"?
│   ├─ K is small vs N         → Min-heap of size K → O(N log K)
│   └─ Values bounded / small   → Bucket sort → O(N)
│
├─ Merging K sorted sequences?
│   └─ Min-heap of (value, source) → LC 23
│
└─ Streaming / running statistic?
    ├─ Median                   → Two heaps (LC 295)
    ├─ K-th largest in stream   → Min-heap of size K
    └─ Top K frequencies live   → Heap + counter

---

Java Heap Cheat Sheet

// Min-heap (default)
PriorityQueue<Integer> minH = new PriorityQueue<>();

// Max-heap (reversed comparator)
PriorityQueue<Integer> maxH = new PriorityQueue<>(Comparator.reverseOrder());

// Heap of int[] by index 1 (e.g., (count, value))
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

// API:
pq.offer(x);     // O(log n) insert
pq.peek();       // O(1)   read root
pq.poll();       // O(log n) remove root
pq.size();

---

The “Two Heaps” Idea (for Streaming Median)

maxHeap = lower half (largest of small numbers on top)
minHeap = upper half (smallest of big numbers on top)

Invariant: maxHeap.size() == minHeap.size()  OR  maxHeap.size() == minHeap.size() + 1

addNum(x):
  push x to maxHeap
  push maxHeap.poll() to minHeap   // balance
  if minHeap.size() > maxHeap.size():
      push minHeap.poll() to maxHeap

median():
  if same size  → (maxHeap.peek() + minHeap.peek()) / 2.0
  else          → maxHeap.peek()

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Top K Frequent Elements	347	Medium	Min-heap / bucket

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Merge K Sorted Lists	23	Hard	Min-heap of heads
2	Find Median from Data Stream	295	Hard	Two heaps

---

Java Implementation Tips

• PriorityQueue is unordered iteration — never trust pq.toArray() order.
• For tie-breaking, supply a Comparator chain: Comparator.comparingInt(...).thenComparing(...).
• For large heaps with custom objects, store references, not full copies — heap ops shuffle elements around.
• Comparator.reverseOrder() works only for Comparable types (Integer, String).
• For int[] heap with custom comparator, prefer subtraction (a,b)->a[0]-b[0] only when values are bounded — use Integer.compare(a[0], b[0]) to avoid overflow.

---

Senior Mental Trigger

“Top-K → size-K heap. K-way merge → heap of K heads. Streaming median → two heaps balanced.”