Member 14049864 Ответов: 0

Реализуйте минимальную кучу с помощью списка списков

Я пытаюсь реализовать минимальную кучу, используя список списков целых чисел. У меня есть рабочий код, чтобы сделать это как таковой, но мой код недостаточно эффективен. Мне было интересно, что кто-то может помочь мне оптимизировать мой код, так как я понятия не имею, что делать в этот момент.

Примечание: каждый список уже упорядочен в порядке возрастания.

Что я уже пробовал:

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

0 Ответов