Heap and Priority Queue Patterns
A heap answers one question well: what is the smallest or largest thing here. It cannot find anything else, and that limitation is what makes it cheap. The recurring interview use is top k, where a heap of size k costs O(n log k) instead of sorting everything, and the recurring surprise is the direction: a min-heap holds the k largest, because its root is both the answer and the cheapest thing to evict.
Where to start, and what comes next
- 01
Top K Elements
The core pattern and the one that appears most. Get the direction right here and the rest follows.
- 02
K-Way Merge
Merging k sorted sequences with a heap of size k, which is the structure behind external sorting.
- 03
Two Heaps
Two heaps facing each other to hold a running median. A genuinely clever use and a common hard question.
- 04
Reorganize / Schedule
Scheduling and rearranging by frequency, where the heap orders by count and the feasibility check comes before the loop.
If you only have time for three things
- A min-heap of size k for the k largest, and a max-heap of size k for the k closest. The root is always the item you are willing to lose.
- Two heaps for a running median, with the rebalance that keeps their sizes within one of each other.
- Knowing that building a heap from n items is O(n), while inserting them one at a time is O(n log n).
Top k has three reasonable answers and the best one depends on the input: sorting at O(n log n), a heap at O(n log k), and quickselect at O(n) on average. Naming all three and picking one with a reason is a stronger answer than producing the heap immediately. If the data streams rather than sitting in an array, the heap is the only one of the three that still works.
The idea underneath
Need the K largest? Use a min-heap of size K. Anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.
Problems that use these patterns
Head to head
Questions people ask
Why a min-heap for the k largest?
Because the root is the smallest of the k best seen so far, which makes it both the current kth largest and the correct thing to discard when something better arrives. A max-heap would put the wrong element within reach.
Can I remove an arbitrary element from a heap?
Not cheaply. Finding it is O(n) since a heap has no search order. The usual workaround is lazy deletion: mark it removed and discard it when it surfaces at the top, which is what sliding-window median implementations have to do.
Does iterating a PriorityQueue give sorted order?
No, and this surprises people regularly. The array is heap-ordered, not sorted. Only repeated poll calls produce sorted output.