Coding interview pattern
Keep the largest or smallest element instantly available without fully sorting.
The idea
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
Cost
| 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
Translatable skeleton
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
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
In the interview
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.
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.
Keep going
These techniques share moves with this one, so the practice carries over.
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Halve the search space each step over any monotonic condition, not just sorted arrays.
Solve overlapping subproblems once, store the results, and build the answer up.
See all coding patterns, the coding questions for your role, and the behavioral round.