合并使用优先级队列K-有序列表 [英] Merging K- Sorted Lists using Priority Queue

问题描述

我一直在问我的算法类做一个K-方式合并算法是的O（nlogk）
搜索后，我发现它可以通过制作A K长度优先级队列和每个列表的第一个元素入队不能做到。提取最低，其追加到结果和从入队的元素已经被提取的列表。
我感到困惑：

I have been asked in my algorithm class to make a K-way merge algorithm which is of O(nlogk) After searching i found it could be done via making a k length priority queue and enqueuing it with the first element of each list. Extract the minimum, append it to result and enqueue from the list whose element has been extracted. I am confused about:

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

1. How will it know when a particular list is exhausted, suppose a list has smaller elements than every other element in other lists?

它如何知道是哪个列表中（如果structue不是用来定义）的元素？

How will it know the element was of which list (if a structue is not used to define)?

是怎样的时间复杂度 O（nlogk）？

编辑：

这将是一个多一点有益的，如果有人能写下来的算法分步进行，因为所有我读它在句子，它很难理解事情是这样的，如果有人可以在算法写下来可能会有所帮助理解了。

It would be a bit more helpful if someone can write down the algorithm step-wise, because all i have read it is in sentences and its hard to understand the way it is, if someone could write down the algorithm might be helpful to understand.

推荐答案

下面是一些Python code，做了合并。

Here's some Python code that does the merging.

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日志K）？那么对于删除的每个值，有一堆流行和可能的堆推（这两者都是为O（log k））的。既然我们删除n个元素，它是O（N日志K）。

Why is it O(n log k)? Well for each value removed, there's a heap pop and possibly a heap push (both of which are O(log k)). Since we remove n elements, it's O(n log k).

这篇关于合并使用优先级队列K-有序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！