Как реализовать приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы?

Question

[FaxWeb]

решаю задачу "4. Приоритетная очередь" на стр.11 https://informatics.msk.ru/pluginfile.php/5946/mod....

В условии указано 2 правила для данной задачи:
1) Процедуры просеивания не должны перемещать элемент дальше, чем это
действительно необходимо. Например, если A[i] =A[2*i], то вызов
Sift_Up(2*i) не должен менять местами эти два элемента (хотя их обмен и не
испортит кучу, он бесполезен).
2) Если при просеивании вниз можно перемещать рассматриваемый элемент
как влево вниз, так и вправо вниз (это бывает, когда он меньше двух равных
дочерних), то следует выбирать направление влево.
Втрое правило довольно произвольно и введено лишь для обеспечения однозначности ответа. Первому правилу, напротив, должна удовлетворять любая
разумная реализация кучи.

Если второй пункт мне понятен, и я учел его, то в первом пункте мне не понятно как связаны индексы i и 2*i, думаю именно из-за этого мое решение не проходит часть тестов. Подскажите как исправить мой код, прикрепляю его ниже:

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct MaxHeap{
    int size = 0;
    int maxCapacity;
    vector<ll> arr;
    MaxHeap(int n) : maxCapacity(n) {
        arr.reserve(maxCapacity);
    }

    pair<int, ll> extractMax(){
        if (size == 0) return pair<int, ll>(-1, -1);

        pair<int, ll> res = {0, arr[0]};
        arr[0] = arr[--size];
        int current = 0;
        while (2*current+1 < size){
            int maxP = (arr[2*current+1] >= arr[2*current+2] ? 2*current+1 : 2*current+2);
            if (arr[current] < arr[maxP]){
                swap(arr[current], arr[maxP]);
                current = maxP;
                res.first = maxP+1;
            } else {
                break;
            }
        }
        return res;
    }

    int add(ll num){
        if (size == maxCapacity) return -1;

        int current = size;
        arr[size++] = num;
        while (current > 0 && arr[(current-1)/2] < arr[current]){
            swap(arr[(current-1)/2], arr[current]);
            current = (current-1)/2;
        }
        return current+1;
    }
};

int main(){
    int n, m;
    cin >> n >> m;

    MaxHeap heap(n);
    for (int i = 0; i < m; i++){
        int command;
        cin >> command;
        if (command == 1){
            pair<int, ll> res = heap.extractMax();
            if (res.first == -1) {
                cout << -1 << endl;
            }
            else {
                cout << res.first << " " << res.second << endl;
            }
        } else {
            ll num;
            cin >> num;
            cout << heap.add(num) << endl;
        }
    }

    for (int i = 0; i < heap.size; i++) {
        cout << heap.arr[i] << " ";
    }

    return 0;
}

Answer 1

[Wataru]

то в первом пункте мне не понятно как связаны индексы i и 2*i

Если нумерация массива идет с 1, то два ребенка элемента i будут 2*i и 2*i+1. У вас же нумерация с 0, т.ч. у вас дети - 2*i+1 и 2*i+2.

Первое условие достигается правильной расстановкой строгого и нестрогого неравнества в условиях в алгоритме.

Похоже, проблема в том, что у вас нумерация с 0 и, если новый элемент оказывается итак максимальным, вы вернете индекс 0, вместо нужного 1. Если вы элемент вниз просеиваете, то у вас там +1 стоит в res.first, но изначально у вас-то там 0.

Далее, вы вектор неправильно используете. Вы делаете reserve и потом работаете с пустым вектором, как-будто он фиксированного размера. Вам надо делать resize вместо reserve. Или еще лучше, вместо вашей переменной size вы используйте arr.size(). При изменении размера массива делайте pop_back() и push_back().

Comments

[FaxWeb]

По поводу вектора я понял, напутал я с reserve и resize. Но если говорить об индексах, то это вы правильно подметили про случай с новым максимальным элементом, и я поменял строку с созданием пары res{0, arr[0]} на res{1, arr[0]}, теперь этот случай учтен и несколько тестов мне это прибавило, но все равно все тесты такой код не закрывает :(

[Wataru]

FaxWeb, давайте новый код

[Wataru]

FaxWeb, А, вот еще ошибку нашел:

while (2*current+1 < size){
            int maxP = (arr[2*current+1] >= arr[2*current+2] ? 2*current+1 : 2*current+2);

У вершины может быть 0, 1 или 2 ребенка. И вот в случае, если 2*current+1==size-1, как раз есть только левый ребенок. А вы все-равно залезете в правого ребенка и может даже туда спустите.

Надо добавить условие, что если второго ребенка нет, то не надо элементы сравнивать - идем точно влево.

[FaxWeb]

ошибку с 1 ребенком тоже учел, но она мне правильных тестов не прибавила

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct MaxHeap{
    int maxCapacity;
    vector<ll> arr;
    MaxHeap(int n){
        maxCapacity = n;
    }

    pair<int, ll> extractMax(){
        if (arr.size() == 0) return pair<int, ll>(-1, -1);

        pair<int, ll> res = {1, arr[0]};
        arr[0] = arr.back();
        arr.pop_back();
        int current = 0;
        while (2*current+1 < arr.size()){
            int maxP;
            if (2*current+1 == arr.size()-1){
                maxP = 2*current+1;
            } else {
                maxP = (arr[2*current+1] >= arr[2*current+2] ? 2*current+1 : 2*current+2);
            } 
            
            if (arr[current] < arr[maxP]){
                swap(arr[current], arr[maxP]);
                current = maxP;
                res.first = maxP+1;
            } else {
                break;
            }
        }
        return res;
    }

    int add(ll num){
        if (arr.size() == maxCapacity) return -1;

        int current = arr.size();
        arr.push_back(num);
        while (current > 0 && arr[(current-1)/2] < arr[current]){
            swap(arr[(current-1)/2], arr[current]);
            current = (current-1)/2;
        }
        return current+1;
    }
};

int main(){
    int n, m;
    cin >> n >> m;

    MaxHeap heap(n);
    for (int i = 0; i < m; i++){
        int command;
        cin >> command;
        if (command == 1){
            pair<int, ll> res = heap.extractMax();
            if (res.first == -1) {
                cout << -1 << endl;
            }
            else {
                cout << res.first << " " << res.second << endl;
            }
        } else {
            ll num;
            cin >> num;
            cout << heap.add(num) << endl;
        }
    }

    for (int i = 0; i < heap.arr.size(); i++) {
        cout << heap.arr[i] << " ";
    }

    return 0;
}

[Wataru]

FaxWeb, Да вроде уже не вижу никаких ошибок. Может, тесты кривые?

[FaxWeb]

Wataru, может и тесты кривые, но тестов я не знаю, загружаю свои решения сюда: https://informatics.msk.ru/mod/statements/view.php...

А так еще заметил в условии что extractMax может и 0 выводить в качестве индекса:
В ответ на запрос типа 1 следует вывести:
• Если извлекать было нечего (очередь пуста), то -1.
• Иначе, как и в предыдущей задаче – два числа: первое – индекс конечного положения элемента после его просеивания (если же удалён был
последний элемент и просеивать осталось нечего, вывести 0); второе –
значение извлечённого элемента.

код который раз поменял, но ничего не изменилось

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct MaxHeap{
    int maxCapacity;
    vector<ll> arr;
    MaxHeap(int n){
        maxCapacity = n;
    }

    pair<int, ll> extractMax(){
        if (arr.size() == 0) return pair<int, ll>(-1, -1);

        pair<int, ll> res = {1, arr[0]};
        arr[0] = arr.back();
        arr.pop_back();
        int current = 0;
        if (arr.size() == 0) return pair<int, ll> (-2, -2);
        while (2*current+1 < arr.size()){
            int maxP;
            if (2*current+1 == arr.size()-1){
                maxP = 2*current+1;
            } else {
                maxP = (arr[2*current+1] >= arr[2*current+2] ? 2*current+1 : 2*current+2);
            } 

            if (arr[current] < arr[maxP]){
                swap(arr[current], arr[maxP]);
                current = maxP;
                res.first = maxP+1;
            } else {
                break;
            }
        }
        return res;
    }

    int add(ll num){
        if (arr.size() == maxCapacity) return -1;

        int current = arr.size();
        arr.push_back(num);
        while (current > 0 && arr[(current-1)/2] < arr[current]){
            swap(arr[(current-1)/2], arr[current]);
            current = (current-1)/2;
        }
        return current+1;
    }
};

int main(){
    int n, m;
    cin >> n >> m;

    MaxHeap heap(n);
    for (int i = 0; i < m; i++){
        int command;
        cin >> command;
        if (command == 1){
            pair<int, ll> res = heap.extractMax();
            if (res.first == -1) {
                cout << -1 << endl;
            } else if (res.first == -2){
                cout << 0 << endl;
            } else {
                cout << res.first << " " << res.second << endl;
            }
        } else {
            ll num;
            cin >> num;
            cout << heap.add(num) << endl;
        }
    }
    for (int i = 0; i < heap.arr.size(); i++) {
        cout << heap.arr[i] << " ";
    }

    return 0;
}

[Wataru]

FaxWeb, Какое кривое условие. Вы в этом случае не "0" выводите, а "0 число".

Т.е. возвращайте не -2, -2, а 0, arr[0]

[FaxWeb]

Wataru, да, так все тесты прошел, что-то действительно криво

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct MaxHeap{
    int maxCapacity;
    vector<ll> arr;
    MaxHeap(int n){
        maxCapacity = n;
    }

    pair<int, ll> extractMax(){
        if (arr.size() == 0) return pair<int, ll>(-1, -1);

        pair<int, ll> res = {1, arr[0]};
        arr[0] = arr.back();
        arr.pop_back();
        int current = 0;
        if (arr.size() == 0) {
            res.first = -2;
            return res;
        }
        while (2*current+1 < arr.size()){
            int maxP;
            if (2*current+1 == arr.size()-1){
                maxP = 2*current+1;
            } else {
                maxP = (arr[2*current+1] >= arr[2*current+2] ? 2*current+1 : 2*current+2);
            } 

            if (arr[current] < arr[maxP]){
                swap(arr[current], arr[maxP]);
                current = maxP;
                res.first = maxP+1;
            } else {
                break;
            }
        }
        return res;
    }

    int add(ll num){
        if (arr.size() == maxCapacity) return -1;

        int current = arr.size();
        arr.push_back(num);
        while (current > 0 && arr[(current-1)/2] < arr[current]){
            swap(arr[(current-1)/2], arr[current]);
            current = (current-1)/2;
        }
        return current+1;
    }
};

int main(){
    int n, m;
    cin >> n >> m;

    MaxHeap heap(n);
    for (int i = 0; i < m; i++){
        int command;
        cin >> command;
        if (command == 1){
            pair<int, ll> res = heap.extractMax();
            if (res.first == -1) {
                cout << -1 << endl;
            } else if (res.first == -2){
                cout << 0 << " " << res.second << endl;
            } else {
                cout << res.first << " " << res.second << endl;
            }
        } else {
            ll num;
            cin >> num;
            cout << heap.add(num) << endl;
        }
    }

    for (int i = 0; i < heap.arr.size(); i++) {
        cout << heap.arr[i] << " ";
    }

    return 0;
}