Merge k sorted streams lazily

Question

You are handed k sorted input streams (think: per-exchange tick files, each ordered by timestamp). Produce a single iterator that yields every element in global sorted order. The streams may be enormous or even unbounded, so you may not read them fully into memory, hold at most one pending element per stream. Target O(N \log k) total time for N elements, and O(k) memory.

Accepted Answer

Prime a min-heap with the first element of each stream, tagged by its stream index. Repeatedly pop the smallest, yield it, and advance that one stream, pushing its next element if any remain. The index tag is a tiebreaker so the heap never has to compare two payloads that happen to be equal (and it keeps output stable by stream order). Everything is lazy: we only ever hold k elements plus the k iterators. Tracing the example: the heap starts {(1,0), (2,1), (3,2)}. Pop 1, pull 4 from stream 0; pop 2, pull 5; pop 3, pull 6; then 4, 5, 6, 7 drain in order, output 1..7. Building via heapify is O(…

Merge k sorted streams lazily

Your answer

More Coding questions