Heap & Priority Queue
01 / The shared mechanism
A heap gives you cheap access to the extreme — the min or the max — while everything else stays in a loose, half-sorted shape. Three sub-patterns: one heap for top-k, two heaps for the running median, and a min-heap of source pointers for merging k sorted streams.
01 / The one-sentence essence
To merge K sorted streams, keep a min-heap of one entry per stream — every pop is the next smallest across all streams, and you only ever pay O(log K) per element.
Problemmerge K sorted listsK3listsL0=[1,4,7] L1=[2,5,9] L2=[3,6,8]
L0
1
4
7
L1
2
5
9
L2
3
6
8
heap (value, src, idx)
— empty —
out
·
3 sorted lists. Seed a min-heap with the head of each — the heap will always hold one frontier per source.
step
0 / 22
|heap|
0
|out|
0
heap min
—
0 / 22
02 / The pattern signature
# merge K sorted lists into one sorted outputheap ← min-heap[ ] # keys = (value, src, idx)for s in 0..K−1:if lists[s] not empty:heap.push((lists[s][0], s, 0))while heap not empty:(val, s, i) ← heap.pop()out.append(val)if i + 1 < |lists[s]|:heap.push((lists[s][i+1], s, i + 1))# tuple ordering: ties broken first by src, then by idx — stable
03 / When to recognize this pattern
"merge K sorted lists / files"
The literal canonical signal. A pairwise merge would cost
O(N · K); the heap brings it to O(N log K) by always keeping K open pointers."external sort"
Sort chunks that fit in memory, write them out, then merge the chunks with a heap. This is how databases sort tables that don't fit in RAM.
"kth smallest across multiple structures"
The kth element of a sorted matrix, the kth smallest sum from two sorted arrays, the kth smallest pair distance — all are k-way merge in disguise.
"smallest range that hits every list"
Maintain one frontier element per list in a heap; the spread between the heap's min and the current global max is a candidate range.
04 / Common pitfalls
i.
Pushing the whole list into the heap at once.
The whole point is to keep the heap at size K, not N. Push only the head of each list initially; advance one source at a time as you pop. Otherwise you've just done an
O(N log N) sort with an extra step.ii.
Forgetting the tuple — keys must carry the source.
The heap stores
(value, src, idx). Without the source pointer you have no way to advance the correct list after popping. Without the index you can't fetch the next element. Both must travel with the value.iii.
Comparators that crash on equal values.
Tuple-ordered heaps with custom keys must define an order on ties — usually by source index. Some libraries (Python's
heapq on objects, Java's PriorityQueue<ListNode>) will compare the second tuple element if the first ties; make sure it's comparable, or supply a comparator.05 / Go practice — on LeetCode
Four problems. The first is the canonical formulation. The next two are k-way merge in disguise — a sorted matrix and a pair-sums table. The last is the classic "smallest range" variant.
— / When to use which
top-k
Use when you need the k most extreme values — not the full sorted order.
stream · O(N log k) · LC 215 / 347 / 703
two heaps
Use when you need the running median — split the data into a low half (max-heap) and a high half (min-heap).
median · max-heap + min-heap · LC 295
k-way merge
Use when you have k sorted streams and need the next-smallest across all of them.
merge · (val, src, idx) · LC 23 / 378