3

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

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

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

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

编辑：

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

4

7 回答 7

7

这是一些进行合并的 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)。

于 2013-10-20T07:42:25.607 回答
2

与其简单地将每个列表的第一个元素存储在优先级队列中，不如将其包装在这样的结构中；

struct wrapper
{
    int list_number;
    int element;
}

然后，当您将元素推入优先级队列时，只需将列表编号形式添加到它所在的位置。这样，当最小元素被弹出时，您将通过检查知道应该从哪个列表中推送下一个要推送到队列中的元素popped_element.list_number。

为了确定您的列表是否为空，您应该向其中添加一个函数，如果列表没有更多元素则empty返回，否则返回false。true该功能将很容易实现。只需检查大小是否为零，然后列表为空，否则它有一个或多个元素。

根据您的问题，我假设使用二进制堆来实现优先级队列。二叉堆中的插入操作需要O(lg k)时间，而 extract-min 操作也需要O(lg k)时间，其中k堆的大小（在您的情况下为列表数）。现在，如果您拥有的元素总数是n，处理所有元素的总时间将是O(n lg k)。

于 2013-10-20T07:44:09.587 回答
2

几年前，在讨论对大型文本文件进行排序时，我写了一系列关于此的文章。这个想法是你放在堆上的项目不仅包含值，还包含值来自的列表。或者，您可以将列表引用放在堆上，并让比较函数与特定列表中的第一项进行比较。

有关基本的解释，请参见http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=676和http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=677使用顺序列表代替堆的算法。有关使用堆的改进版本，请参阅http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=680 。

正如我在评论中所说，您也可以在没有堆的情况下进行合并。有关说明，请参阅https://stackoverflow.com/a/18984961/56778。

于 2013-10-21T15:21:54.497 回答
0

当没有更多元素时，1 个列表已用尽

2 您需要跟踪最小元素 com 来自哪个列表

3 对于每个元素，您将其放入大小为 k 的最小堆中，该堆需要 logk，因此您有 n 倍 logk

于 2013-10-20T07:31:33.860 回答
0

您不应该在这里表​​示所有列表中的“n”节点总数，而不仅仅是一个列表。在这种情况下，解决方案是 O(n logk)。如果我们的意思是我们在每个列表中平均有 n 个节点（总共 k 个列表），那么它将是 O(nk logk)

这是一些代码的深入解释

于 2014-04-24T02:14:03.433 回答
0

Paul Hankin 的解决方案是正确的，但它有点难以阅读，尤其是你想用 c++ 或 java 实现。我的解决方案类似于保罗的。如果你用 c++ 或 java 编写，你可能需要一个额外的数据结构来存储元素的值、第 k 个数组中元素的索引和列表中数组的索引。

Element{
    int value;
    int idInArray,
    int idInList
}

但是在python中，我只是存储在一个元组中（值，idInArray，idInList）

def mergeKArray(*lists):
    # implemented by min heap
    h = []
    r = []
    for k, arr in enumerate(lists):
        heapq.heappush(h, (arr[0], 0, k))
    while h:
        # min is the minimum element
        # i is the index of the min in the k-th array
        # k is the index of array in the list
        min, i, k = heapq.heappop(h)
        r.append(min)
        if i < len(lists[k]) - 1:
            i += 1
            heapq.heappush(h, (lists[k][i], i, k))
    return r

因为我只需要维护一个包含 k 个元素的最小堆，所以弹出或注入堆的时间是 O(log k)。我还需要扫描所有 n 个元素，每个元素花费 2*log(k) 时间来注入和弹出。因此，大 O 为 O(n*log k)。

于 2016-05-12T14:20:59.703 回答
0

这是我使用 c++ stl 的代码

#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#define ROWS 4
#define COLS 8
using namespace std;

struct node
{
    int ele;
    int arr_no;
    int next_index; 
};

void printVector(vector<int> v)
{
    for(unsigned int i=0;i<v.size();i++)
        cout<<v[i]<<" ";
}

// THIS IS THE BASIS ON WHICH THE ELEMENTS OF A PRIORITY QUEUE ARE SORTED AND 
// KEPT IN THE QUEUE, HERE THE CRITERIA IS THAT THE NODE WITH SMALLER ELEMENT SHOULD
// COME ABOVE THE ONE WITH LARGER ELEMENT

class compare
{
    public:
        bool operator()(node& n1, node& n2)
        {
           if (n1.ele > n2.ele) 
                return true;
           else
                return false;
        }
};

vector<int> mergeKArrays(vector< vector<int> > v)
{
    int k = v.size();       // NUMBER OF LISTS
    int n = v.at(0).size(); //SIZE OF EACH LIST

    vector<int> result;
    //result.resize( n*k );

    priority_queue<node, vector<node>, compare> minHeap;
    for (int i = 0; i < k; i++)
    {
        node temp;
        temp.ele = v[i][0]; //STORE THE FIRST ELEMENT
        temp.arr_no = i;        //INDEX OF ARRAY
        temp.next_index = 1;    //INDEX OF NEXT ELEMENT TO BE STORED FROM ARRAY
        minHeap.push(temp);
    }

    // NOW ONE BY ONE GET THE MINIMUM ELEMENT FROM MIN
    // HEAP AND REPLACE IT WITH NEXT ELEMENT OF ITS ARRAY
    for (int count = 0; count < n*k; count++)
    {
        // GET THE MINIMUM ELEMENT AND STORE IT IN OUTPUT
        node min_ele_node = minHeap.top();
        minHeap.pop();      
        result.push_back(min_ele_node.ele);

        // FIND THE NEXT ELELEMENT THAT WILL REPLACE CURRENT
        // ROOT OF HEAP. THE NEXT ELEMENT BELONGS TO SAME
        // ARRAY AS THE CURRENT ROOT.
        node new_node;
        new_node.arr_no = min_ele_node.arr_no;
        if (min_ele_node.next_index < n)
        {
            new_node.ele = v.at(min_ele_node.arr_no)[min_ele_node.next_index];
            new_node.next_index = min_ele_node.next_index + 1;
        }
        // IF ROOT WAS THE LAST ELEMENT OF ITS ARRAY
        else 
        {
            new_node.ele =  INT_MAX; //INT_MAX IS FOR INFINITE
        }

        // REPLACE ROOT WITH NEXT ELEMENT OF ARRAY
        minHeap.push(new_node);
    }
    return result;
}


int main()
{
    int arr[ROWS][COLS] = 
                    { 
                        {10, 20, 30, 40, 50, 60, 71, 86},
                        {15, 25, 35, 45, 60, 69, 77, 78},
                        {27, 29, 37, 48, 50, 65, 75, 78},
                        {32, 33, 39, 50, 80, 133, 139, 150},
                    }; 

    vector< vector<int> > matrix ;

    for( int i=0 ; i < ROWS; i++)
    {
        vector<int> vec;
        for(int j=0; j < COLS; j++)
            vec.push_back(arr[i][j]);
        matrix.push_back(vec);
    }

    vector<int> result = mergeKArrays(matrix);
    printVector(result);
    return 0;
}
于 2017-10-08T10:16:21.900 回答