Merge Sorted Iterators with a Heap Generator in Python

Merge multiple sorted iterators into a single sorted stream using a heap and generator, yielding values lazily in order.

Medium Python 3.9+ Aug 9, 2026 Comprehensions & generators 15 views 0 copies

heapq generator merge sorted lazy

Python code

27 lines

Python 3.9+

import heapq

def merge_sorted_iterators(*iterators):
    heap = []
    for idx, iterator in enumerate(iterators):
        try:
            value = next(iterator)
            heapq.heappush(heap, (value, idx, iterator))
        except StopIteration:
            continue

    while heap:
        value, idx, iterator = heapq.heappop(heap)
        yield value
        try:
            next_value = next(iterator)
            heapq.heappush(heap, (next_value, idx, iterator))
        except StopIteration:
            continue


if __name__ == "__main__":
    it1 = iter([1, 4, 7])
    it2 = iter([2, 5, 8])
    it3 = iter([3, 6, 9])
    merged = merge_sorted_iterators(it1, it2, it3)
    print(list(merged))

Output

stdout

[1, 2, 3, 4, 5, 6, 7, 8, 9]

How it works

The function uses a min-heap to track the smallest current value from each iterator, storing tuples of (value, index, iterator) so heap operations are deterministic. On each yield, it pops the smallest value and refills the heap from that same iterator, maintaining overall sorted order. Using a generator means values are produced lazily, so you don't materialize the entire merged sequence unless you explicitly ask for it. The index breaks ties when values are equal, ensuring stable ordering across iterators.

Common mistakes

Forgetting the index in the heap tuple, which causes an error when two values are equal
Not catching StopIteration when a shorter iterator is exhausted, causing premature termination
Using iterators instead of lists as inputs, requiring manual conversion before passing

Variations

Use heapq.merge repeatedly (but it only handles two iterators at a time, chaining results)
Convert all iterators to lists first, then use sorted(sum(iterables, [])) for small data

Real-world use cases

Merging multiple sorted API result pages into one unified feed without loading everything into memory.
Combining sorted log streams from different servers into a single chronological sequence for analysis.
Interleaving sorted database result sets across shards during a paginated backup or export job.

Merge Sorted Iterators with a Heap Generator in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Comprehensions & generators

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Comprehensions & generators

Keep learning

Tutorials

Quizzes