在我的算法课上有人要求我制作一个 O(nlogk)
的 K 路合并算法
搜索后我发现可以通过制作一个 k 长度的优先级队列并将其与每个列表的第一个元素一起排队来完成。提取最小值,将其附加到结果并从其元素已被提取的列表中排队。
我很困惑:
它如何知道特定列表何时用完,假设一个 列表中的元素比其他列表中的所有其他元素都小?
它如何知道元素属于哪个列表(如果不使用结构来定义)?
时间复杂度
O(nlogk)
如何?
编辑:
如果有人能逐步写下算法会更有帮助,因为我读过的都是句子,很难理解它的方式,如果有人能写下算法可能会有所帮助理解。
最佳答案
下面是一些执行合并的 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)。
关于arrays - 使用优先队列合并 K 排序列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19474924/