c++ - 合并排序 k 列表 c++

Question

我有一个随机生成的排序列表列表，我必须在堆的帮助下将大列表合并排序为一个最终列表。

std::list<int> randomList(int size)
{
    std::list<int> list;
    for (int i = 0; i < size; i++)
        list.push_back(rand());
    list.sort();
    return list;
}

std::list<list<int>> generateListOfLists(int size, int elements)
{
    std::list<list<int>> bigList;
    std::list<int> aux;
    for (int i = 0; i < size; i++)
    {
        aux = randomList(elements);
        bigList.push_back(aux);
    }
    return bigList;
}

我使用列表的原因是我必须这样做。任何人都可以帮助我了解如何在这里实现合并排序吗？

谢谢!

Answer 1

为所有列表创建一个迭代器数组。从所有列表中生成一堆最小元素。

在进行合并时，您的堆应该始终只包含每个列表中的一个元素。在您的主循环中，从堆中获取最小元素，确定它来自哪个列表，增加该列表的迭代器，并将堆中的元素替换为相应列表中的下一个元素。

要将列表索引附加到元素，请将 struct 存储在您的堆中:

struct data
{
    int element;
    int list;
};
std::vector<data> heap;
...
std::pop_heap(heap.begin(), heap.end());
... // Your data is in the last position of the array: heap.back()
std::push_heap(heap.begin(), heap.end());