Lesson 18.5 · Heaps and Priority Queues
K-Way Merge
Merge K sorted sources by keeping one candidate from each in a min-heap: always take the smallest, then refill from the same source.
10 min
Think of it like this
Three queues at a ticket desk, each already sorted by ticket number. The clerk looks only at the front person of each queue and serves the lowest number, and then that queue's next person steps up.
1.The heap holds K fronts
Store (value, which source, position) in the heap. Pop the smallest, output it, and push the next element from the same source. With N total elements, that's O(N log K).
The same idea handles sorted linked lists (Merge K Sorted Lists in Module 8), rows of a sorted matrix, and "smallest range covering one element from each list".
lists = [[1, 4], [2, 5], [3, 6]]heap(list)
output(list)
empty
Step 1/4Start with the front of each list.
Remember
- Heap size is K, not N.
- Store where each value came from.
- O(N log K).
Common mistakes
- Concatenating and sorting everything (O(N log N), ignores the sorted input).