Задать вопрос
@FaxWeb

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

решаю задачу "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;
}
  • Вопрос задан
  • 91 просмотр
Подписаться 1 Средний Комментировать
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
то в первом пункте мне не понятно как связаны индексы 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().
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы