-1

Помогите, пожалуйста отладить мой код. В программировании полный 0.

В этой задаче вам необходимо организовать структуру данных Heap для хранения целых чисел, над которой определены следующие операции:

Insert(X) — добавить в Heap число X; Extract — достать из Heap наибольшее число (удалив его при этом).

Эту задачу нужно решить без использования встроенных структур данных для поиска максимального числа. Входные данные

Во входном файле записано количество команд n (1 ≤ n ≤ 100 000), потом последовательность из n команд, каждая в своей строке.

Каждая команда имеет такой формат: "0 <число>" или "1", что означает соответственно операции Insert(<число>) и Extract. Добавляемые числа находятся в интервале от 1 до 107 включительно.

Гарантируется, что при выполнении команды Extract в структуре находится по крайней мере один элемент. Выходные данные

В выходной файл для каждой команды извлечения необходимо вывести число, полученное при выполнении команды Extract.

Вот мой код:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class SimpleBinaryHeap {

    vector<int> heap_data;

public:

    void insert(int value) {

        heap_data.push_back(value);

        int index = heap_data.size() - 1;
        int parent = (index - 1) / 2;

        while(index > 0 && heap_data[parent] < heap_data[index]) {

            swap(heap_data[parent], heap_data[index]);

            index =  parent;
            parent = (index - 1) / 2;

        }

    }

    int extract(int& i, int& num){
        int j = i;
        int cl = i * 2 + 1;
        if(cl < num && heap_data[cl] > heap_data[j])j = cl;
        int cr = cl + 1;
        if(cr < num && heap_data[cr] > heap_data[j])j = cr;
        if(i == j) return heap_data[0];
        swap(heap_data[i], heap_data[j]);
        extract(j, num);
        return heap_data[0];
    }

};

int main() {

    SimpleBinaryHeap bh;

    int command;

    int num;
    cin >> num;

    for(int i = 0; i < num; i++) {
        cin >> command;
        if(command == 0) {
            int value;
            cin >> value;
            bh.insert(value);
        }
        if(command == 1) {
            cout << bh.extract(i, num) << endl;
        }
    }
    return 0;
}
2
  • что у вас именно не работает? 21 июл 2021 в 17:15
  • Например на тесте 7 0 100 0 10 1 0 5 0 30 0 50 1 ответ 100 100 (надо 100 50)
    – xsafter
    21 июл 2021 в 18:04

1 ответ 1

1

Тут стоит уточнить какая куча тебе нужна, если она нужна например для сортировки то вектор подойдет, но сама куча должна отвечать свойствам, таким что: предок узла всегда больше его потомков. А значит максимум будет находиться наверху позволяя его оперативно извлечь. Кучи обычно используются в очередях с приоритетом чтобы за O(log(n)) извлечь максимум. Ты что делаешь ты, немного странно, это больше походит на сортировку. Тебе надо использовать явно не вектор, так как он не позволяет оперативно извлекать элемент, в плохом раскладе при использовании постоянных сортировок это O(nlog(n)), а при вставке по значению, так чтобы вектор хранился всегда отсортированным это O(n). Если же требуется сама куча, неважно какой скорости, то проще сортировать после вставки в конец и извлекать последний элемент

>>> код
vector <int> data;
void insert(int num){
    data.push_back(num);
    sort(data.begin(),data.end());
}
int eraseMax(){
    int mm = data.back();
    data.pop_back();
    return mm;
}

Это кончено костыль, но что поделать если ты хчоешь все делать через вектора. В ином случае, если вы хотите кучу кучей, то вам нужно реализовать биномиальную, самую простую из них, тогда будет и вставка за log и удаление за log. Вот тут о ней можно почитать

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.