Many sorted streams, one output
The k way merge pattern combines several already sorted lists into one sorted result. It generalizes the merge step of merge sort from two lists to any number. You see it when merging sorted files, finding the smallest range covering all lists, or returning the kth smallest across sources.
A heap of front runners
The trick is to always know which list offers the smallest next value without scanning all of them.
- Place the first element of each list into a min heap, tagged with which list it came from.
- Repeatedly pop the smallest, append it to the output, and push the next element from that same list.
- Continue until the heap empties.
Because the heap only ever holds one candidate per list, it stays the size of the number of lists, and each pop and push is cheap.
Why the heap stays small
You never load whole lists into the heap. At any moment it holds at most one front runner from each source, so even merging huge streams needs only modest memory proportional to the number of lists.
Key idea
Hold one front element per sorted list in a min heap, repeatedly emit the smallest and refill from its source, merging all lists in one ordered pass.