Merge sorted event streams into one timestamp-ordered iterator

Several event streams are each already sorted by timestamp. Build an iterator that returns all their events as one stream in timestamp order, reading lazily: never load a whole stream into memory or collect and sort everything up front.

Interface

Unless you agree on a different interface with the interviewer, assume:

• MergedStream(streams: list[Iterator[tuple[int, str]]]) — each stream yields (timestamp, payload) in non-decreasing timestamp order. Some may be empty.
• has_next() -> bool — whether any event is left, without consuming one.
• next() -> tuple[int, str] — the next event overall. Equal timestamps come from the lower-numbered stream first, and keep their order within a stream. Raises StopIteration when nothing is left.

Example

s = MergedStream([iter([(1, "a"), (3, "b")]), iter([]), iter([(1, "c"), (2, "d")])])
s.has_next()  -> True
s.next()      -> (1, "a")
s.next()      -> (1, "c")      # tie at 1: stream 0 before stream 2
s.next()      -> (2, "d")
s.next()      -> (3, "b")
s.has_next()  -> False

s = MergedStream([iter([(2, "x"), (2, "y")]), iter([(1, "p"), (2, "q")]), iter([(5, "z")])])
# -> (1, "p"), (2, "x"), (2, "y"), (2, "q"), (5, "z")

Constraints

• Up to 10^4 streams and 2 * 10^5 events in total.
• Extra memory O(k) for k streams: one pending head per stream that still has events.
• next in O(log k).

Clarifying questions

• How are ties on the timestamp broken: by stream number, arrival, or not at all?
• Are the streams finite, or can they be endless (live feeds)?
• Can reading a stream block or fail? Should one slow stream hold up the others?
• Should duplicates across streams be dropped?

What a strong answer covers

• A min-heap of (timestamp, stream_index, payload) seeded with each stream's first event. After popping an event, push the next event from the same stream only.
• Why stream_index in the key both breaks ties as required and stops Python from comparing payloads.
• Empty streams skipped at the start; streams that run out simply leave the heap.
• O(log k) per event and O(k) memory; compare with merging pairs repeatedly (O(n log k) total too, but more passes).
• Tests: no streams, all empty, one stream, many ties, and a check against sorted on small inputs.

Follow-ups

• Streams are live sources that may block. How do you decide it is safe to emit an event (watermarks, or waiting for every stream's head)?
• Events can arrive up to a few seconds late within a stream. Reorder with a bounded buffer.
• The streams are files too big for memory on different machines. Merge them across machines.
• Add peek() and make the iterator restartable from a checkpoint.