Click here to Skip to main content
16,017,788 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I'm trying to implement a min heap using a list of lists of integers. I have working code to do as such but My code is not efficient enough. I was wondering I someone could help me optimize my code as I have no idea what to do at this point.

Note: Every list is already ordered in ascending order.

What I have tried:

C++
void organizeLists(std::vector<std::list<int>>& lists, std::vector<int>& output) {
    Comp comp;
    for (std::vector<std::list<int>>::iterator listMember=lists.begin(); listMember!=lists.end();) {
        if(listMember->empty()) {
            listMember = lists.erase(listMember);
        } else {
            ++listMember;
        }
    }
    if(!lists.empty()) {
        std::make_heap(lists.begin(), lists.end(), comp);
        while (!lists.empty()) {
            std::list<int> &temp = lists.front();
            output.push_back(temp.front());
            temp.pop_front();
            if (temp.empty()) {
                lists.erase(lists.begin());
            }
            std::make_heap(lists.begin(), lists.end(), comp);
        }
    }
}
Posted
Updated 9-Nov-18 11:55am
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900