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 track the k most extreme elements out of N, keep a heap of size k whose root is the worst of the k — every new element either kicks the root out or doesn't.
Problemtop k largest from a streamStream[3, 1, 5, 12, 2, 11, 7, 8]k3
stream
30
11
52
123
24
115
76
87
— heap is empty —
heap = [ ]
Keep a min-heap of size k = 3. The root is the smallest of the top-k — any new element strictly larger kicks the root out.
step
0 / 17
heap size
0
min (root)
—
action
init
0 / 17
03 / The pattern signature
# top-k largest — min-heap of size kheap ← [ ]for x in stream:if |heap| < k:heap.push(x)elif x > heap[0]:heap.replace_root(x)return sort(heap, descending)# top-k smallest: max-heap and the dual comparison
04 / When to recognize this pattern
"top k / kth"
You need the k most or least extreme — not the full sorted order. The whole point is to spend less than
O(N log N)."streaming / online"
Elements arrive one at a time and you can't see them all at once. A heap of size k gives a constant-memory answer no matter how long the stream is.
"frequency / weighted"
The "extreme" relation isn't on the raw value — it's on a derived key like a count or a distance. Same algorithm, different comparator.
"running quantile / percentile"
The kth-largest of a window or stream is exactly what a size-k heap maintains for free. For the running median, two heaps are required — see two-heaps.
05 / Common pitfalls
Using a max-heap to find the largest.
For top-k largest you want a min-heap of size k — the root is the smallest of the keepers, and incoming larger elements kick it out. A max-heap of size k would put the biggest seen so far on top and never let you cheaply check the kth element.
Strict
> vs non-strict ≥ when replacing.With strict
>, an incoming element equal to the root is rejected — the existing duplicate stays. With ≥, it gets cycled in. The two produce the same set on inputs without duplicates; on duplicates, they differ. Match your problem.Reaching for a heap when sort is fine.
If you already have all N elements in memory and k is close to N, sorting is simpler and competitive. The heap wins when N ≫ k or the data is streaming and you can't buffer all of it.
06 / Go practice — on LeetCode
easy3
medium19
01Kth Largest Element in an Array— LC 215→02Ugly Number II— LC 264→03Super Ugly Number— LC 313→04Top K Frequent Elements— LC 347→05Kth Smallest Element in a Sorted Matrix— LC 378→06Sort Characters By Frequency— LC 451→07Task Scheduler— LC 621→08Find K Closest Elements— LC 658→09Top K Frequent Words— LC 692→10K-th Smallest Prime Fraction— LC 786→11K Closest Points to Origin— LC 973→12Single-Threaded CPU— LC 1834→13Seat Reservation Manager— LC 1845→14Process Tasks Using Servers— LC 1882→15Remove Stones to Minimize the Total— LC 1962→16Find the Kth Largest Integer in the Array— LC 1985→17Minimum Operations to Halve Array Sum— LC 2208→18Smallest Number in Infinite Set— LC 2336→19Max Sum of a Pair With Equal Sum of Digits— LC 2342→
— / 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