Heaps and Priority Queues: An Interview Playbook
When to reach for a heap, the classic patterns (top K, merging streams, scheduling), and Python/Java/C++ mental models.
Heaps and Priority Queues: An Interview Playbook
A heap is the data structure you want when the problem repeatedly asks for the best among a changing set (smallest, largest, closest, soonest).
The two interview families
1) Top K / threshold maintenance
Keep the heap size bounded. Examples: top K frequent elements, K closest points, median from a stream (often two heaps).
2) Merge / schedule by time
Push candidates into a min-heap ordered by next event time. Examples: merge K sorted lists, task scheduler variants, Dijkstra-lite situations on small graphs.
Complexity checklist
Implementation traps
heapq is a min-heap. For max-heap tricks, negate values or store tuples carefully.Pattern recognition drill
When you read a problem, ask:
If both answers lean yes, sketch the heap before you reach for sorting everything.
Practice pairing means solving one heap problem timed, then redoing it the next day from a blank file. The second pass should feel boring, and that is the point.