合并排序k列表C ++

2024-05-04 • 问答

我有一个随机生成的排序列表列表，我必须借助堆将大列表排序成一个最终列表。

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;
}

我使用列表的原因是因为我必须这样做。谁能帮助我了解如何在此处实现合并排序？

谢谢！

为所有列表创建一个迭代器数组。从所有列表中堆出最少的元素。

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

要将列表索引附加到元素，请将struct s存储在堆中：

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());

合并排序k列表C ++

lihuizi0806 回答：合并排序k列表C ++

大家都在问