PATTERN 12: Heap / Priority Queue Thinking

D

Qubits of DPK

April 11, 2026

Core DSA

Core Idea (lock this)

“I need fast access to the
You are not sorting once.
You are continuously choosing the current optimal candidate.
If sorting gives you global order,
Heap gives you dynamic order.

How to Recognize This Pattern (CRITICAL)

You should instantly think Heap / Priority Queue when:
  • You see:
  • The data:
  • The problem says:
Trigger words:
  • “most frequent”
  • “closest”
  • “minimum cost”
  • “schedule”

30 MUST-DO INTERVIEW PROBLEMS

(10 Easy → 10 Medium → 10 Hard)

EASY (1–10): Heap Familiarity

Goal: remove fear of heaps.
  1. #
    Last Stone Weight – LC 1046
  2. #
    Relative Ranks – LC 506
  3. #
    Find Median from Data Stream – LC 295
  4. #
    Minimum Cost to Connect Sticks – LC 1167
  5. #
    Top K Frequent Words – LC 692
  6. #
    Kth Largest Element in a Stream – LC 703
  7. #
    Find the Kth Largest Integer in the Array – LC 1985
  8. #
    Reduce Array Size to The Half – LC 1338
  9. #
    Longest Happy String – LC 1405
  10. #
    Maximum Product of Two Elements in an Array – LC 1464
After these:
Using a heap should feel as natural as using an array.

️ MEDIUM (11–20): Heap as a Decision Tool

Heap is now part of the strategy, not just a container.
  1. #
    Merge K Sorted Lists – LC 23
  2. #
    Kth Largest Element in an Array – LC 215
  3. #
    Task Scheduler – LC 621
  4. #
    Reorganize String – LC 767
  5. #
    Minimum Number of Refueling Stops – LC 871
  6. #
    IPO – LC 502
  7. #
    Maximum Subsequence Score – LC 2542
  8. #
    Smallest Range Covering K Lists – LC 632
  9. #
    Ugly Number II – LC 264
  10. #
    Furthest Building You Can Reach – LC 1642
Interviewers check:
Do you know why and how

HARD (21–30): Greedy + Heap Mastery

These prove senior-level decision making.
  1. #
    Course Schedule III – LC 630
  2. #
    Maximum Performance of a Team – LC 1383
  3. #
    Minimum Cost to Hire K Workers – LC 857
  4. #
    Sliding Window Median – LC 480
  5. #
    Design Twitter – LC 355
  6. #
    All O`1 Data Structure – LC 432
  7. #
    Find Median from Data Stream (Full Design View) – LC 295
  8. #
    Maximum Profit in Job Scheduling – LC 1235
  9. #
    Shortest Path in Binary Matrix (Dijkstra variant) – LC 1091
  10. #
    Trapping Rain Water (Heap approach) – LC 407
These demand:
  • Heap + Greedy reasoning
  • Understanding when to undo a greedy choice

The ONE Rule That Wins Interviews

Always be able to answer:
“Why can’t sorting solve this problem?”
If the answer is:
  • “Because the best choice keeps changing”
Heap is justified.

Common Interview Mistakes

  • Sorting when dynamic choice is needed
  • Using heap but not explaining why max-heap vs min-heap
  • Forgetting heap size represents constraint (K, capacity, deadline)

INTERVIEW REVISION CARD — Pattern 12

1️⃣ Pattern in One Line

"When the best choice keeps changing dynamically, use a heap to always access the current optimum in O(log N)."

2️⃣ Recognize It When...

  • Streaming data or dynamically changing input
  • Need top K, Kth largest/smallest repeatedly
  • Trigger words: "most frequent", "closest", "minimum cost", "schedule", "at each step"
  • Sorting once isn't enough — order changes after each operation

3️⃣ Don't Confuse With...

  • Sorting (P6) → sort gives static order; heap gives dynamic order
  • Monotonic Stack (P8) → stack resolves nearest; heap gives global best
  • Greedy (P9) → greedy makes choices; heap is the data structure enabling those choices

4️⃣ Approach in 3 Steps

  1. #
    Decide: min-heap (smallest first) or max-heap (largest first)?
  2. #
    Push elements; pop when size exceeds K or condition triggers
  3. #
    Justify: "why can't sorting solve this?" — because best changes dynamically

5️⃣ Invariant to Maintain

"At every step, the heap contains exactly the K best candidates seen so far."

6️⃣ Complexity to Justify

  • Push/Pop: O(log K) per operation
  • Total: O(N log K)
  • Space: O(K)
  • Why: Heap maintains partial order — only K elements tracked

7️⃣ Edge Cases to Always Check

  • K larger than array size
  • All elements same
  • Negative numbers in min/max heap
  • Empty heap before polling
  • K = 1 — just track min/max directly

8️⃣ One Line to Say in Interview

"Sorting won't work here because the optimal choice changes dynamically — I'll use a min/max heap to always access the current best in O(log K), giving O(N log K) overall."