Top-K & k-way merge
When you need only the best k of many items, or the next item from several sorted sources, a heap of size k does it in O(n log k), without sorting everything.
To keep the k best, keep a small heap that faces the other way
Two families of problems share one trick. Top-k problems ask for the k largest, smallest or most frequent items out of many. Sorting everything works, at O(n log n), but sorts far more than you need. Instead, keep only the k best seen so far, in a min-heap. Its root is the weakest of the k you are keeping, the one a newcomer has to beat. If a new item is larger, it goes in and the root comes out. The heap never grows past k, so each item costs O(log k), and the whole job O(n log k) time and O(k) memory.
A k-way merge combines k sorted lists into one. The next item of the output is always the smallest of the k lists' current fronts, and a min-heap of those fronts finds it in O(log k). Take the smallest, then push the next item from the same list.
The rule
For the k largest, keep a min-heap of size k; for the k smallest, a max-heap. The root is the weakest item you are keeping, so each newcomer is compared with it alone. To merge k sorted lists, keep a min-heap of their fronts.
"k" in the question, or several sorted sources
The k largest, smallest, closest or most frequent items
A heap of size k: O(n log k) instead of sorting everything
The kth largest, asked again after every new item
A min-heap of size k; the answer is its root
Several sorted lists, arrays or streams to combine
A k-way merge with a min-heap of the fronts
The kth smallest in a sorted matrix, or among pair sums
A k-way merge: each row or each first item is a sorted source
"Most frequent" or "by count"
Count with a hash map first, then top-k on the counts
The kth largest in a stream is the root of a heap of k
Numbers keep arriving, and after each one you report the kth largest so far. Keep a min-heap of the k largest numbers. A new number is pushed; if that makes k + 1, the smallest is popped, and it might be the newcomer itself. The root is always the answer.
Count first, then keep the top k by count
For the most frequent values, the items being ranked are counts, not the values themselves. Count every value with a hash map, then run the same size-k min-heap over [count, value] pairs. To return the most frequent first, pop the heap from the weakest up and fill the answer from the back.
When k is close to the number of distinct values, sorting the counts is just as good. The heap pays off when k is small and the data is large or arrives as a stream.
A k-way merge always takes the smallest front
Each sorted list's smallest remaining item is its front. The merged list's next item must be the smallest of those fronts, so keep exactly the fronts in a min-heap. Pop the smallest, add it to the output, and push the next item from the same list. A second list, src, kept in step with the heap, records which list each value came from.
Merging the lists into the result one after another would copy early items over and over: O(N × k). The heap handles each item once. On LeetCode the lists are linked lists, and the merge relinks nodes instead of copying numbers; the heap part is the same.
The shape to reuse
- 1function topK(items, k)
- 2 heap ← empty min-heap
- 3 for each x in items
- 4 push x into heap
- 5 if size of heap > k
- 6 pop the smallest from heap
- 7 return heap
- 8
- 9function mergeK(lists)
- 10 heap ← min-heap of every list's first item (skip empty lists)
- 11 while heap is not empty
- 12 x ← pop the smallest from heap
- 13 output x
- 14 if x's list has a next item
- 15 push that item into heap
After topK, the heap holds the k largest items and its root is the kth largest.
Flip the comparison for the opposite end: a max-heap of size k keeps the k smallest. In Python, push negated values into heapq for a max-heap; in Java, give PriorityQueue a reversed comparator.
Where top-k solutions go wrong
For the k largest you need a min-heap, so the weakest kept item is at the root and is the one evicted. A max-heap of size k would evict the best one.
Pushing everything and popping k times works, but costs O(n log n) and O(n) memory, losing the point of the pattern.
For a single kth largest in a list you hold all at once, the partition-based selection from Merge sort & quicksort is O(n) on average.
A heap of list nodes or [count, value] pairs needs an explicit key: compare .value, or the count. Ties need a rule if the order of the answer matters.
A k-way merge holds one front per list, never more: push a list's next item only when its current front comes out.
3 questions
Remember this
- For the k largest, keep a min-heap of size k: its root is the weakest item kept, so each newcomer is compared with it alone, O(n log k) in all.
- For the most frequent items, count with a hash map first, then run top-k on the counts.
- A k-way merge keeps one front per list in a min-heap: pop the smallest, then push the next item from the same list.
Now solve some yourself
Only this topic 0 of 11 solved
- EasyThe k weakest rows of a grid
- EasyThe kth largest so far, after each new number
- EasyA subsequence of length k with the largest sum
- MediumThe kth largest number, with a heap of size k
- MediumThe k points nearest the origin
- MediumThe kth largest of numbers written as strings
- MediumThe kth smallest value in a grid with sorted rows and columns
- MediumThe k pairs with the smallest sums
- MediumThe nth number made only of factors 2, 3 and 5
- HardThe running median of a stream
- HardThe smallest range that touches every list
Mixed with topics you have practiced 0 unlocked
6 more once you have practiced Linked lists, Hash tables & maps, Greedy algorithms, Sliding window, Prefix sums. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next