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.
02 / 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
03 / 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
04 / 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.
05 / Common pitfalls
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.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.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.06 / Go practice — on LeetCode
medium11
01Sort List— LC 148→02Ugly Number II— LC 264→03Super Ugly Number— LC 313→04Find K Pairs with Smallest Sums— LC 373→05Kth Smallest Element in a Sorted Matrix— LC 378→06K-th Smallest Prime Fraction— LC 786→07Minimum Cost to Connect Sticks— LC 1167→08Path With Minimum Effort— LC 1631→09Single-Threaded CPU— LC 1834→10Divide Intervals Into Minimum Number of Groups— LC 2406→11Maximal Score After Applying K Operations— LC 2530→
hard8
01Merge k Sorted Lists— LC 23→02Find Median from Data Stream— LC 295→03IPO— LC 502→04Smallest Range Covering Elements from K Lists— LC 632→05Kth Smallest Number in Multiplication Table— LC 668→06Find K-th Smallest Pair Distance— LC 719→07Minimize Deviation in Array— LC 1675→08Find the K-Sum of an Array— LC 2386→
— / 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