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

一尘不染

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

algorithm

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

假设一个列表的元素比其他列表中的所有其他元素小，那么如何知道特定列表何时用尽？
如何知道元素属于哪个列表（如果不使用结构来定义）？
时间复杂度如何O(nlogk)？

编辑：

如果有人可以逐步写下该算法，那会有所帮助，因为我所读的全部内容都是句子，很难理解它的方式，如果有人可以写下该算法可能会有所帮助。

阅读 312

2020-07-28

共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）。

2020-07-28