Heap / Priority Queue: when to spot it, explain it, and practice it
Heap problems are about maintaining a moving frontier. If you keep asking for the next best, next smallest, or current top-k choice, a priority queue often gives you the right balance of speed and clarity.
Pattern coverage
40+
Best first move
Decide whether you need a min heap, max heap, or two heaps.
Common failure point
Using the wrong heap polarity and then writing inverted logic everywhere.
When this pattern should come to mind
Checklist before you code
The solving flow that works well in interviews
Define what the heap top represents in one sentence.
Push new candidates as soon as they become eligible.
Pop only when the top no longer belongs in the frontier or the size is too large.
If two heaps are used, rebalance after every insertion or removal.
Convert the final heap state back into the required answer format.
Common variants
Top-k maintenance
Keep the best k candidates seen so far.
Merge frontier
Pick the next smallest head across multiple sorted lists or streams.
Dual-heap balance
Use two heaps when you need both lower-half and upper-half information.
Template preview
import heapq
heap = []
heapq.heappush(heap, value)
smallest = heapq.heappop(heap)
# max heap in Python
heapq.heappush(heap, -value)
largest = -heapq.heappop(heap)
Classic problems with useful framing
#215
Kth Largest Element in an Array
The cleanest top-k maintenance question.
Find the kth largest element in an unsorted array.
#23
Merge k Sorted Lists
Shows why heaps are perfect for multiple sorted streams.
Merge k sorted linked lists into one sorted list.
#295
Find Median from Data Stream
Classic dual-heap balancing problem.
Maintain a data structure that returns the median after each insertion.
#347
Top K Frequent Elements
A practical frequency + heap interview staple.
Return the k most frequent elements in the array.
A more useful problem ladder for practice
This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.
Foundation
#215 Kth Largest Element in an Array
Find the kth largest element in an unsorted array.
You do not need full sorting; you only need to remember the best k values seen so far.
Foundation
#347 Top K Frequent Elements
Return the k most frequent elements in the array.
The heap should compare by frequency, not by value itself.
Variant depth
#23 Merge k Sorted Lists
Merge k sorted linked lists into one sorted list.
The heap never needs whole lists, only the current head of each unfinished list.
Variant depth
#295 Find Median from Data Stream
Maintain a data structure that returns the median after each insertion.
One heap stores the lower half, the other stores the upper half, and their sizes differ by at most one.
High-frequency mistakes
Using the wrong heap polarity and then writing inverted logic everywhere.
Forgetting to cap the heap size in top-k problems.
Not cleaning stale entries when the heap stores delayed state.
Comparing the wrong field when tuples contain multiple priorities.
Recommended practice path
Start with kth largest and top-k frequency.
Then do merge-k-lists and interval scheduling style heaps.
Add two-heap median problems after that.
Finish with harder frontier-expansion questions such as smallest range or meeting rooms.