When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Top k
- Streaming rank
- Merge sorted inputs
When another approach fits better
- All output must be fully ordered once
- Priorities are only small bounded integers better served by buckets
How it works#
Resort all candidates after every insertion or fully sort n items when only k matter.
Choose heap direction from the element you need to evict or consume.
Insert each candidate and restore the size bound immediately.
For multi-source merge, store the next item plus enough source state to advance only that source.
InvariantFor bounded top-k, the heap contains exactly the best k processed candidates and its root is the weakest retained one.
Example and template#
Kth Largest Element in an Array
Compare a bounded heap with sorting and selection algorithms.
Open the full problem brief- Keep k=3
heap [4, 9, 7]The root 4 is the weakest retained top-three value.
- Read 8
push 8; pop 4 → [7, 9, 8]The invariant is restored immediately.
heap = empty min_heap
for item in stream:
push item
if size(heap) > k:
pop minimum
return root as kth largest- Time
- O(n log k)
- Space
- O(k)
- Assumptions
- Comparison is O(1) and the heap is bounded to k for selection.
Pitfalls#
Common wrong approaches
A max-heap cannot directly expose the weakest member of a retained largest-k set.
Keeping all n values loses the intended space and time advantage.
Edge cases
- k is one
- k exceeds item count
- Equal priorities
- Stale priorities after updates
Interview narration
- “I only need the largest k, so the rest can be discarded permanently.”
- “A min-heap exposes the weakest retained candidate.”
- “After each insertion I cap the heap at k, preserving exactly the processed top-k.”
Practice#
Kth Largest Element in an Array
Compare a bounded heap with sorting and selection algorithms.
Practice this problemContinuously report the third-highest score from an event stream.
Reveal the pattern decision
Maintain a size-three min-heap; full sorting after every event repeats unnecessary work.
Transfer problem
Merge several timestamp-sorted service queues into one ordered stream.
Checkpoint: Heap one head per queue and carry queue/index identity to advance the correct source.
Follow-up variations
- Support deletions with lazy invalidation
- Compare quickselect when the input is static and only one rank is requested
Error-log prompts
- Which candidate should the root expose?
- Was heap size bounded immediately?