How does a min-heap merge k sorted input streams into one ordered output stream?
answer
- how many candidates can be the next output?
- one live element per source at a time
- the heap holds k entries, never N
- each entry remembers which source it came from
- extract smallest, then refill from that same source
basics
~20 sKeep only the current head of each of the k streams in a min-heap. Repeatedly extract the smallest, emit it, and push that same stream's next element in its place. The heap never grows beyond k entries.
solid answer
~50 sThe insight is that the next element of the merged output can only be the current head of one of the k streams, so you never need more than k candidates in flight. Seed a min-heap with one entry per stream, each entry carrying the value plus the identifier of the stream it came from. Then loop: extract the minimum, emit its value, and push the successor from that same stream. The source identifier is what makes the refill possible — without it you know the winning value but not where to pull the next candidate. With N elements total, every element is inserted once and extracted once from a heap of size at most k, giving `O(N log k)` time and `O(k)` extra space. Crucially the input is consumed lazily: you hold k elements, not N, so streams larger than memory still merge.
go deeper
Be ready to state the loop out loud: seed the heap with one head per source, extract the minimum, emit it, push the successor from that same source. Say why the heap size is k and not the total element count.
Explain why the next output element can only be one of the k heads, and derive the O(N log k) bound from one insert and one extract per element. Point out that the source identifier is what makes the refill step possible.
Show the operational value: bounded memory and incremental output mean you can merge feeds far larger than RAM and let a consumer read before the inputs finish. Note where per-source read buffering, not the heap, dominates memory.
Own the framing that this pattern converts a memory-bound sort into a streaming pipeline. Be ready to argue when a merge belongs in the data path at all versus pushing ordering upstream to the producers or an index.
## The problem shape You operate a fleet of 200 servers. Each one writes its own log file, and each file is already in timestamp order because each server appends as events happen. Now you want a single chronological feed across the whole fleet for incident review. You have 200 sorted sequences and want one sorted sequence — that is the k-way merge, with k = 200. ## The key observation At any moment, what is the next line of the merged feed? It must be the oldest line that has not been emitted yet. Because every source is internally sorted, the oldest unemitted line of any source is that source's *current head*. So the global next line is the minimum over just k values — one per source — not a minimum over all N remaining lines. That single observation is the whole pattern. You never need more than k live candidates, and a min-heap is exactly the structure that gives you "smallest of k" repeatedly while accepting replacements cheaply. ## The loop 1. **Seed.** For each source i, take its first element and insert it into the min-heap. Each heap entry is a composite record: the ordering value (here, the timestamp), the source identifier i, and the position within that source. 2. **Extract.** Pull the minimum out of the heap. That value is the next element of the merged output; emit it. 3. **Refill.** The extracted entry came from source i. Take the *next* element of source i and insert it. If source i has nothing left, insert nothing — the heap simply shrinks. 4. **Repeat** until the heap is empty. An empty heap means every source has been drained. At every point the heap holds at most one entry per source, so its size is bounded by k, and it starts at k and only shrinks as sources run dry. ## Why the source identifier matters A beginner version stores only the values. Then the extraction tells you *what* the smallest value was but not *which* source produced it, so you cannot fetch its successor — and if you re-scan the sources to find out, you have thrown away the entire advantage. Storing the source identifier (and, if the source is not itself a cursor you can advance, the position within it) is not a decoration; it is the mechanism. ## The cost Every one of the N elements enters the heap exactly once and leaves exactly once. Each of those two operations costs `O(log k)` because the heap holds at most k entries. Total: `O(N log k)` time. Extra space is `O(k)` for the heap itself, plus whatever buffering each source needs. Compare the naive alternative of concatenating all 200 files and sorting the result: that is `O(N log N)` comparisons and, worse, it requires all N lines resident at once. With 200 servers' worth of logs, N is enormous and k is 200. `log k` is about 8 while `log N` might be 30, and the memory difference is the difference between "runs on a laptop" and "does not run". ## What the pattern buys beyond speed - **Streaming.** Output is produced incrementally. The consumer can start reading the merged feed before the inputs have been fully read, and you can stop early if you only wanted the first few thousand lines. - **Bounded memory.** Memory depends on k and the per-source buffer size, not on the data volume. This is precisely why the pattern underpins merging phases in disk-based sorting: the whole dataset never has to fit. - **Order preservation within a source.** Because a source's next element only enters the heap after its predecessor has left, elements of one source can never be emitted out of order relative to each other. ## Recognising it in an interview Interviewers rarely say "use a heap". They say: "you have many already-sorted feeds and need one merged feed", or "give me the smallest values across many sorted sequences without materialising everything". Both descriptions are the same machine: heap of heads, extract, emit, refill. The moment you hear *many* sorted inputs and *one* sorted output, size the heap at k, not at N, and remember to tag each entry with where it came from. A final calibration: when k is small — two or three sources — the heap is technically correct but constant factors make a direct comparison of the heads simpler and faster. The heap earns its keep when k is large enough that scanning all k heads on every emitted element would itself dominate.
- Why does each heap entry have to carry its source identifier?Because the refill step is source-specific. After extracting the minimum you must push the successor from the very source that just lost its head, and nothing else about the extracted value tells you which one that was. Without the identifier you would have to rescan all k sources to find the successor, which turns an `O(log k)` step into an `O(k)` one and destroys the bound.
- What does the heap approach give you that concatenating everything and sorting does not?Two things. Cost: `O(N log k)` instead of `O(N log N)`, and with many sources k is far smaller than N. More importantly, memory: sorting the concatenation needs all N elements resident, while the merge holds only k heads plus per-source buffers. That is what lets you merge inputs far larger than available memory and start emitting output immediately instead of after the last input is read.
- If k is only 2, is the heap still the right tool?Correct, but overkill. With two sources `log k` is 1, so the asymptotic bound is the same as simply comparing the two heads directly, and the heap adds allocation and bookkeeping constants for nothing. The heap starts paying off when k is large enough that scanning every head on each emitted element would itself dominate the runtime.
Two hundred queues of people, each queue already ordered by arrival time. You only ever compare the 200 people standing at the front; when one is let through, only that queue steps forward.
saying these in an interview costs you the question
- Puts all N elements into one heap instead of k heads
- Stores only values, so the successor cannot be fetched
- Claims the merge is O(N log N) regardless of k
- Assumes all inputs must be fully loaded before merging
- Re-sorts the whole output after merging to be safe