使用优先级队列合并K排序列表

这是一些合并的Python 2代码。

import heapqdef addtoheap(h, i, it):    try:        heapq.heappush(h, (next(it), i))    except StopIteration:        passdef mergek(*lists):    its = map(iter, lists)    h = []    for i, it in enumerate(its):        addtoheap(h, i, it)    while h:        v, i = heapq.heappop(h)        addtoheap(h, i, its[i])        yield vfor x in mergek([1, 3, 5], [2, 4, 6], [7, 8, 9], [10]):    print x

为什么是O（n log k）？好吧，对于每个删除的值，都有一个堆弹出消息，可能还有一个堆推送消息（两者都是O（log
k））。因为我们删除了n个元素，所以它是O（n log k）。