Слияние сортировки k списков c ++ - PullRequest
Новая
       30

Слияние сортировки k списков c ++

1 голос
/ 04 ноября 2019

У меня есть случайно сгенерированный список отсортированных списков, и мне нужно объединить сортировать большой список в один окончательный список с помощью кучи. 

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

Причина, по которой я использую списки, заключается в том, чтоМне пришлось. Может кто-нибудь помочь мне с идеей, как я могу реализовать сортировку слиянием здесь?

Спасибо!

1 Ответ

1 голос
/ 04 ноября 2019

Создайте массив итераторов для всех ваших списков. Создайте кучу минимальных элементов из всех списков.

При объединении ваша куча всегда должна содержать ровно один элемент из каждого списка. В вашем основном цикле получите минимальный элемент из кучи, определите, из какого списка он получен, увеличьте итератор для этого списка и замените элемент в куче следующим элементом из соответствующего списка.

Toприкрепить индекс списка к элементу, хранить 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());
...