DSA & Algorithms
Part 13 of 21 · DSA Interview PatternsHeaps, Priority Queues & Top-K — n-largest, Merge K & Streaming
Min/max heaps for top-K, merge K lists, and streaming extremes.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You want the top k, or the next extreme in a stream
Prefer
A heap of size k
A min-heap of the k largest values: if the new value beats the root, the root leaves.
- O(n log k) beats a full sort when k is small.
- Python's heapq is a min-heap. Negate for a max-heap.
- Merge K lists holds one head from each list.
Alternative
Sort the whole input
Right answer, wrong cost, and it does not work as a stream.
- A max-heap when you meant the kth largest.
- Forgetting the frequency count before the heap on top-K frequent.
- Calling a full sort a streaming algorithm.
Keep only k winners
The root of a size-k min-heap is the smallest winner, which is the kth largest.
- 1
Push while the heap is under k
The first k values are the initial winners. - 2
Replace the min when the new value wins
heapreplace drops the root and inserts. - 3
Stop there
The heap is unordered. Sort it only if you must print it sorted.
Overview
Min/max heaps for top-K, merge K lists, and streaming extremes.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use a heap (priority queue) for repeated extract-min/max, top-K, and merging sorted streams.
Recognition cues
- kth largest / top K frequent
- merge k sorted lists
- median from data stream (two heaps)
- Dijkstra uses binary heap
Mental model
Decisions
- 1
Step 1 Read the next element x
- nextStep 2 Min-heap size below k?
- ?
Step 2 Min-heap size below k?
- yesStep 3a Push x
- noStep 3b x greater than the heap min?
- max-heap of all n insteadFailure path - O(n log n) time and O(n) memory
- 3
Step 3a Push x
- nextStep 5 More input?
- ?
Step 3b x greater than the heap min?
- yesStep 4a heapreplace - pop min, push x
- noStep 4b Skip x
- 5
Step 4a heapreplace - pop min, push x
- nextStep 5 More input?
- 6
Step 4b Skip x
- nextStep 5 More input?
- ?
Step 5 More input?
- yesStep 1 Read the next element x
- noStep 6 Heap holds the k largest - O(n log k)
- 8
Step 6 Heap holds the k largest - O(n log k)
- 9
Failure path - O(n log n) time and O(n) memory
Lesson map
Heaps, Priority Queues & Top-K — n-largest, Merge K & Streaming
Min/max heaps for top-K, merge K lists, and streaming extremes.
Architecture. Step 1 Read the next element x Ready. Step 2 Min-heap size below k? Ready. Step 3a Push x Ready. Step 3b x greater than the heap min? Ready. Step 4a heapreplace - pop min, push x Ready. Step 4b Skip x Ready. Step 5 More input? Ready. Step 6 Heap holds the k largest - O(n log k) Ready. Failure path - O(n log n) time and O(n) memory Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB A["Step 1 Read the next element x Ready"] H["Step 2 Min-heap size below k? Ready"] P["Step 3a Push x Ready"] C["Step 3b x greater than the heap min? Ready"] R["Step 4a heapreplace - pop min, push x Ready"] S["Step 4b Skip x Ready"] N["Step 5 More input? Ready"] T["Step 6 Heap holds the k largest - O(n log k) Ready"] F["Failure path - O(n log n) time and O(n) memory Ready"] A -->|continues| H H -->|yes| P H -->|no| C C -->|yes| R C -->|no| S P -->|continues| N R -->|continues| N S -->|continues| N N -->|yes| A N -->|no| T H -->|max-heap of all n instead| F
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Top-K via size-k heap: O(n log k) time, O(k) space.
- Full sort: O(n log n).
- Merge K lists: O(N log k) for N total elements.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Kth Largest Element in an Array
- Top K Frequent Elements
- Merge k Sorted Lists
- Find Median from Data Stream
- K Closest Points to Origin
- Task Scheduler
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Why size-k min-heap for kth largest?
Answer
Root is the smallest among current top k = kth largest.
Top-K frequent?
Answer
Count with hash; heap by frequency; or bucket sort by count.
Two-heap median?
Answer
Max-heap lo, min-heap hi; balance sizes; tops give median.
Merge K complexity?
Answer
O(N log k) with heap of k heads.
Heap vs Quickselect?
Answer
Quickselect average O(n) for kth; heap better for streaming top-k.
Dijkstra?
Answer
Binary heap prioritizes next closest node.