Heap and Priority Queue Problems in Coding Interviews: A Practical Guide
Heap and Priority Queue Problems in Coding Interviews: A Practical Guide
Heaps show up in interviews more often than candidates expect, usually disguised as "find the top k," "merge these sorted things," or "always process the smallest next." If you know three or four heap templates, many of these problems become routine. This guide covers what a heap gives you, the patterns that use it, and how to talk about it clearly.
What a heap actually gives you
A binary heap keeps the smallest (min-heap) or largest (max-heap) element at the top. You get:
push: O(log n)popthe top: O(log n)peekat the top: O(1)- build from a list (heapify): O(n)
That's it. A heap does not give you fast search or sorted iteration. If you catch yourself needing "find any element quickly," you probably want a hash map or a balanced tree instead.
In Python, heapq is a min-heap. For a max-heap, push negated values or tuples like (-priority, item). In Java, use PriorityQueue with a comparator. Know your language's version before the interview so you don't waste minutes on syntax.
Pattern 1: Top k elements
"Return the k largest numbers" or "the k most frequent words." The key insight is to keep a min-heap of size k. Push each element; if the heap grows past k, pop the smallest. At the end, the heap holds the k largest.
import heapq
def k_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap
This runs in O(n log k), which beats sorting (O(n log n)) when k is small. Saying that comparison out loud is an easy way to show you understand the trade-off.
Pattern 2: Merge k sorted lists
Put the first element of each list into a min-heap along with which list it came from. Pop the smallest, append it to the result, and push the next element from the same list. Total cost is O(N log k), where N is the total number of elements.
Watch out for ties: if two entries have equal values, Python will try to compare the next tuple field. Include an index as a tiebreaker, such as (value, list_index, node).
Pattern 3: Running median
Keep two heaps: a max-heap for the lower half and a min-heap for the upper half. After each insert, rebalance so their sizes differ by at most one. The median is the top of the larger heap, or the average of both tops. This is a favorite follow-up because it tests whether you can maintain an invariant under updates.
Pattern 4: Scheduling and "process the cheapest next"
Meeting room allocation, task scheduling with cooldowns, and Dijkstra's shortest path all share one shape: repeatedly pull the next most urgent item. For meeting rooms, sort meetings by start time and keep a min-heap of end times; the heap's size at any moment is the number of rooms in use.
How to explain your choice
Interviewers care less about whether you know heaps exist and more about why you picked one. A good one-line justification sounds like: "I need repeated access to the minimum while elements keep arriving, so a heap gives me O(log n) per operation instead of re-sorting each time."
Common pitfalls
- Using a max-heap for top-k when a size-k min-heap is the efficient choice.
- Forgetting that
heapqis a min-heap and getting results in reverse. - Comparing objects that don't support ordering; add a tiebreaker.
- Claiming heapify is O(n log n). It's O(n), and interviewers occasionally ask.
Practice set
Try Kth Largest Element, Top K Frequent Words, Merge K Sorted Lists, Find Median from Data Stream, and Meeting Rooms II. Do each once with a heap and, where possible, once with an alternative (such as quickselect for kth largest), then compare. Being able to discuss both is what separates a solid answer from a memorized one.
Disclosure: I work on Linkjob AI, which you can find at https://www.linkjob.ai/. It can help during prep, but drilling these four patterns by hand is what makes them stick.