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

Question

在我的算法课上有人要求我制作一个 O(nlogk) 的 K 路合并算法 搜索后我发现可以通过制作一个 k 长度的优先级队列并将其与每个列表的第一个元素一起排队来完成。提取最小值，将其附加到结果并从其元素已被提取的列表中排队。 我很困惑:

1. 它如何知道特定列表何时用完，假设一个 列表中的元素比其他列表中的所有其他元素都小？

2. 它如何知道元素属于哪个列表(如果不使用结构来定义)？

3. 时间复杂度O(nlogk)如何？

编辑:

如果有人能逐步写下算法会更有帮助，因为我读过的都是句子，很难理解它的方式，如果有人能写下算法可能会有所帮助理解。

Answer 1

下面是一些执行合并的 Python 2 代码。

import heapq

def addtoheap(h, i, it):
    try:
        heapq.heappush(h, (next(it), i))
    except StopIteration:
        pass

def 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 v

for 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)。