Heap, selection, and stream · HTML
For m nondecreasing sequences S_j, store the first unconsumed entry (value,j,pos) from every nonempty source. Pop the global minimum and advance only that source.
Recognition signals
- The input consists of sorted lists, linked streams, iterators, or files.
- The global next item must be one of the current source heads.
- Only the first t merged items are needed, so flattening and sorting is wasteful.
- Sources are lazy or too large to coexist in memory.
- Candidates form several independent monotone chains.
False friends
| Signal | Why it is different |
|---|
| Internally unsorted sources | A source can hide a smaller item behind its head; sort each source first or use a general selection method. |
| General graph shortest paths | Dijkstra relaxes shared states reached by multiple routes; K-way merge follows fixed, non-merging ordered chains. |
| Only two in-memory arrays | A two-pointer merge is linear with a smaller constant and needs no heap. |
Core invariant
The heap contains exactly the first unconsumed item of every source that still has data; the global minimum unconsumed item is therefore in the heap.
State, transition, and processing order
| Item | Definition |
|---|
| State | A min-heap of size at most m with entries (key, source_id, source_position). |
| Transition | Pop one head as the next output, advance that source by one, and push its new head if it exists. |
| Frontier / order | The set of heads of m ordered chains; only the chain that just won is expanded. |
Python skeleton
from heapq import heappop, heappush
def merge_sorted(sources):
heap = []
for sid, seq in enumerate(sources):
if seq:
heappush(heap, (seq[0], sid, 0))
out = []
while heap:
value, sid, pos = heappop(heap)
out.append(value)
pos += 1
if pos < len(sources[sid]):
heappush(heap, (sources[sid][pos], sid, pos))
return out
Correctness sketch
- Within one ordered source, its head is its smallest unconsumed item.
- The minimum over all unconsumed items is consequently the minimum over source heads, which heap pop returns.
- Only the winning source loses its head; advancing that source alone restores the invariant.
Complexity
| Time | Space | Parameters |
|---|
| O(N log m) for N outputs, or O(m+t log m) for a t-item prefix | O(m), excluding output | m is the source count, N the total size, and t the consumed prefix. |
Edge cases
- no sources
- empty individual sources
- duplicate values
- payloads requiring a tie-breaker
- lazy iterators without indexing
Error patterns
| Pattern | Why it fails / fix |
|---|
| Pushing every source element | This grows the heap to O(N) and discards the main frontier compression. |
| Advancing every source | Only the winner lost its head; advancing other sources skips valid output. |
| Omitting source identity | After a pop there is no way to know which chain to advance. Carry an id and position or iterator. |
Selection and exclusion rules
- Use two pointers for exactly two materialized sources.
- Use a heap for m ordered sources or a short merged prefix.
- Represent lazy sources by iterators rather than copying them.
- If candidate chains merge into shared states, evaluate Dijkstra semantics.
| Relation | Template | Boundary |
|---|
| composition | Linked-list pointer rewiring | A heap selects linked-list heads while pointer rewiring builds the output. |
| contrast | Top-K bounded heap | Top-K evicts candidates; K-way merge preserves one next candidate per source. |
Original micro-example
| Part | Detail |
|---|
| Result | The output is [1,2,3,5,7,8], and the heap never exceeds three entries. |
| Setup | Three timestamp streams are [1,8], [2,3], and [5,7]. |
| Trace | Heads 1,2,5 enter the heap. After popping 1, only 8 is added; then 2,3,5,7,8 follow. |
Recall prompts
My notes