Union of K Sorted Iterators

Problem

Given k iterators over sorted inputs, produce a single sorted iterator over their union (de-duplicated). Reported MongoDB question, with a k-iterator follow-up.

Example

[1,3,5],[2,3,6] -> 1,2,3,5,6

Constraints

• Iterators may be large/lazy

Approach

Min-heap of (value, iterator); skip duplicates. Discuss lazy evaluation and memory.