Coding interview pattern
Heap / Priority Queue
Keep the largest or smallest element instantly available without fully sorting.
The idea
How the heap / priority queue pattern works
A heap is a tree-shaped structure that gives O(1) access to its minimum (min-heap) or maximum (max-heap) and O(log n) insertion and removal. You reach for it whenever you repeatedly need the current best element from a changing collection, which is exactly the shape of top-K, streaming-median, and merge-K problems. Building it costs O(n); each push or pop costs O(log n).
The top-K pattern is the most common interview use. To find the K largest elements, keep a min-heap of size K: push each element, and whenever the heap exceeds size K pop the smallest. What remains is the K largest, computed in O(n log K) time and O(K) space rather than sorting the whole input. The mirror trick (a max-heap of size K) gives the K smallest. Recognising which heap to use is half the battle.
Heaps also power Dijkstra's shortest path (always expand the nearest unsettled node), event-scheduling and interval problems (the smallest end time on top), and the two-heaps technique for a running median (a max-heap for the lower half, a min-heap for the upper half, kept balanced). The unifying idea is the same: you never need the whole order, only the extreme, so a heap beats a sort.
Recognition
When to reach for it
- You repeatedly need the current min or max of a changing set.
- The question asks for the top K, the K closest, or the Kth largest.
- You are merging several sorted streams.
- You need a running median or to always expand the cheapest frontier (Dijkstra).
Cost
Time & space complexity
| Operation | Time | Space |
|---|---|---|
| Push / pop | O(log n) | O(1) |
| Build heap from array | O(n) | O(1) in place |
| Top K with size-K heap | O(n log K) | O(K) |
Worked example
Walkthrough: Kth largest element in an array
- 1Maintain a min-heap that will hold at most K elements.
- 2Push each array element onto the heap.
- 3Whenever the heap size exceeds K, pop the smallest element.
- 4After processing everything, the heap holds the K largest, and its smallest (the root) is the Kth largest overall.
- 5This runs in O(n log K), beating a full O(n log n) sort when K is small.
Translatable skeleton
The shape in pseudocode
Language-agnostic on purpose. Translate it to your language of choice.
heap = []; for x in nums: heappush(heap, x); if len(heap) > k: heappop(heap); return heap[0]Practice
Curated problem set
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Kth Largest Element in an Array | Medium | Size-K min-heap, the template problem. |
| K Closest Points to Origin | Medium | Heap keyed by distance. |
| Top K Frequent Elements | Medium | Count, then heap by frequency. |
| Merge k Sorted Lists | Hard | Heap of list heads. |
| Task Scheduler | Medium | Greedy with a max-heap of counts. |
| Find Median from Data Stream | Hard | Two heaps kept balanced. |
Avoid these
Common pitfalls
- Using a max-heap where a size-K min-heap is the efficient choice (or vice versa).
- Forgetting most standard libraries provide only a min-heap (negate for max).
- Letting the heap grow to n when size K would do, wasting memory.
- Comparing complex objects without a clear key, breaking the ordering.
In the interview
How to communicate it live
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
For top-K problems, explain the counterintuitive choice of a size-K min-heap for the K largest, since the smallest of the K sits on top ready to be evicted; articulating this is the whole insight.
State the complexity advantage explicitly, O(n log K) with a size-K heap versus O(n log n) for a full sort, so the interviewer sees you chose the heap for a reason, not by habit.
Remember most standard libraries ship only a min-heap; mention that you negate values or invert the comparator to get max-heap behaviour rather than assuming one exists.
Also searched as
priority queue pattern - top k elements - min heap max heap
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- 2.4 Priority Queues (binary heap) Sedgewick and Wayne, Princeton University
- heapq: Heap queue algorithm Python Software Foundation
- PriorityQueue (Java SE 21 & JDK 21) Oracle
Keep going
Related patterns
These techniques share moves with this one, so the practice carries over.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.