Merging multiple sorted sequences.

[Peter Otten]

Erik wrote:

> Hi Peter,
> 
> On 12/04/17 23:42, Peter Otten wrote:
>> Erik wrote:
>>
>>> I need to be able to lazily merge a variable number of already-sorted(*)
>>> variable-length sequences into a single sorted sequence.
>>
>> https://docs.python.org/dev/library/heapq.html#heapq.merge
> 
> AFAICT (looking at the Python 3.5 heapq implementation, albeit very
> briefly), it seems like that is a greedy algorithm. Am I missing
> something?
> 
> Thanks, E.

Watching it at work:

>>> import heapq
>>> def noisy(items, source):
...     for item in items:
...         print("fetching", item, "from", source)
...         yield item
... 
>>> a = noisy(range(0, 10, 2), "a")
>>> b = noisy(range(1, 10, 2), "b")
>>> c = noisy([3.5, 3.6, 5.5], "c")
>>> abc = heapq.merge(a, b, c)
>>> next(abc)
fetching 0 from a
fetching 1 from b
fetching 3.5 from c
0
>>> next(abc)
fetching 2 from a
1
>>> next(abc)
fetching 3 from b
2
>>> next(abc)
fetching 4 from a
3
>>> next(abc)
fetching 5 from b
3.5
>>> next(abc)
fetching 3.6 from c
3.6

Verdict: not greedy ;)