Merge sort k lists c++

Question

I have a randomly generated list of sorted lists and I have to merge sort the big list into one final list with the help of a heap.

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

The reason I'm using lists is because I have to. Can anyone help me with an idea of how I can implement the merge sort here?

Thanks!

Answer 1

Make an array of iterators for all your lists. Make a heap of minimal elements from all the lists.

While doing the merging, your heap should always contain exactly one element from each list. In your main loop, get the minimal element from the heap, determine from which list it came, increase the iterator for that list, and replace the element in the heap with the next element from the corresponding list.

To attach a list index to an element, store structs in your heap:

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