← Create New Paste

Heaps and Priority Queues in Coding Interviews: When and How to Use Them

3 views
Heaps are one of those data structures many candidates learn once and then forget, yet they solve a surprising number of interview problems cleanly. If a question mentions "top K", "k-th largest", "merge sorted lists", "schedule", or "median of a stream", there is a good chance a heap is the intended tool. What a heap gives you A binary heap keeps the smallest (min-heap) or largest (max-heap) element at the top. Inserting and removing the top both cost O(log n), and peeking at the top costs O(1). Building a heap from an existing list costs O(n). In Python you use heapq, which is a min-heap; in Java you use PriorityQueue; in C++ you use priority_queue, which is a max-heap by default. Know your language's default, because flipping it incorrectly is a common bug. Pattern 1: Top K elements To find the K largest elements, keep a min-heap of size K. Push each element; if the heap grows beyond K, pop the smallest. At the end the heap holds the K largest values. This runs in O(n log K) time and O(K) space, which beats sorting when K is small. Explain why a min-heap is used for "largest": the top of the heap is the weakest member of your current top K, so it is the one you evict. Pattern 2: K-way merge For "merge K sorted lists" or "find the smallest range covering elements from K lists", push the first element of each list into a min-heap along with which list it came from and its index. Repeatedly pop the smallest and push the next element from the same list. Total time is O(N log K), where N is the total number of elements. Storing tuples like (value, list_index, element_index) avoids comparison errors when values tie. Pattern 3: Two heaps for running medians To track the median of a stream, keep a max-heap for the lower half and a min-heap for the upper half. After each insertion, rebalance so their sizes differ by at most one. The median is either the top of the larger heap or the average of both tops. Interviewers like this question because it tests whether you can maintain an invariant across operations, so state the invariant explicitly before coding. Pattern 4: Scheduling and greedy choices Problems like "minimum meeting rooms", "task scheduler with cooldown", or "reorganize string so no two adjacent characters match" use a heap to repeatedly pick the best next option. For meeting rooms, sort meetings by start time and keep a min-heap of end times; if the earliest ending meeting finishes before the next starts, reuse that room. Pattern 5: Dijkstra's shortest path Dijkstra's algorithm is a heap problem in disguise. Push (distance, node), pop the closest unvisited node, relax its neighbors. Mention that you skip stale entries when a popped distance is larger than the recorded best, since most standard heaps do not support decrease-key. Common mistakes - Using a max-heap in Python without negating values. - Forgetting that heapq.heapify works in place and returns None. - Pushing objects that cannot be compared when the first fields tie. - Claiming O(n log n) for "top K" when the better answer is O(n log K). - Mentioning quickselect as an alternative is a bonus, but be honest that its worst case is O(n^2). How to talk about it in the room Start by stating the brute force (sort everything, O(n log n)), then say what the heap improves and why. Write a short helper if the tuple logic gets messy, and dry-run three or four pushes and pops so the interviewer sees the heap's contents change. Practice tips Solve one problem from each pattern above, then mix them without looking at the category. If you want support during the real thing, Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews, which some candidates use to keep their reasoning structured under pressure. The core skill, though, is recognizing that "repeatedly need the best next item" means heap.
Created Nov 14, 2026 13:32 Expires Nov 14, 2027 13:32