Heap and priority queue interview questions
A heap gives you the smallest or largest item in constant time and lets you change the collection in logarithmic time. Interviewers reach for it whenever a question keeps asking for the best remaining item.
How do I solve heap and priority queue interview questions?
A heap, or priority queue, always gives you the smallest or largest item in constant time and updates in logarithmic time. Use it for top k elements, merging k sorted lists, a running median with two heaps, and scheduling problems where you repeatedly need the next best item.
Practise heap and priority queue
How to recognise a heap and priority queue problem
The question asks for the k largest, smallest or most frequent items, or the kth item of something.
You repeatedly need the best remaining candidate while new candidates arrive: tasks, meetings, streams, the next smallest from several sorted lists.
Sorting everything works but is wasteful when you only need k items or a running answer.
How to build the solution
For the k largest items, keep a min-heap of size k. For each item, push it, and if the heap has more than k items pop the smallest. At the end the heap holds the k largest. Cost: n log k.
For merging k sorted sequences, push the first item of each with its source, pop the smallest, and push the next item from the same source.
For a running median, keep a max-heap of the lower half and a min-heap of the upper half, and rebalance so their sizes differ by at most one.
Know your language's heap: some are min-heaps only, so a max-heap needs negated values or a comparator.
Classic problems to practise
Kth Largest Element in an Array, Top K Frequent Elements, Merge k Sorted Lists, Find Median from Data Stream, Task Scheduler, K Closest Points to Origin, Meeting Rooms II, Last Stone Weight.
Mistakes interviewers see
Using a max-heap of size k for the k largest items instead of a min-heap of size k, which gives the wrong item to discard.
Sorting the whole input when a heap of size k is enough, and not saying why you chose one.
Forgetting the language default: in Python and Java the built-in heap is a min-heap, in C++ it is a max-heap.
Not breaking ties: when priorities are equal, comparing the next field can fail on items that cannot be ordered.
Practise it as an interview
Take a topic-based interview on heap and priority queue to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.
Frequently asked questions
What is the complexity of a heap?
Push and pop are logarithmic, peeking at the top is constant, and building a heap from n items is linear.
Heap or sorting for top k?
A heap costs n log k and uses k memory; sorting costs n log n. For small k on large input the heap is better, and quickselect gives an average linear answer.