Привет CodeForces! Решаю простую задачу на реализацию кучи(приоритетной очереди). Условие здесь(страница 12, задача 5). Если коротко то мы должны обработать m запросов, каждый запрос может быть трех типов:
1 — извлечь максимальный элемент, вывести его и вывести позицию последнего элемента после просеивания
2 — добавить элемент, вывести его индекс после просеивания
3 — удалить элемент с индексом и вывести сам элемент
Если мы не можем выполнить какую-то операцию надо выводить -1. После выполнения запросов нужно вывести массив в котором хранится куча. До этого я решал такую же задачу где нужно было обрабатывать только запросы 1, 2 и она прошла. Добавил удаление произвольного элемента и не проходит. Я использую такой алгоритм удаления произвольного элемента: ставлю на место этого элемента последний элемент и выполняю sift_up(i) и sift_down(i), где i — индекс удаляемого элемента. Вроде должно работать, но на многих тестах WA. Вот код. Мне кажется алгоритм правильный и у меня есть подозрения что ошибка в коде. Помогите найти ошибку.
long long x = heap[--b]; cout << x << "\n"; // Выводим сам элемент
Так делать нельзя. Элементы в куче не хранятся по порядку, т. есть i-ый элемент необязательно лежит в heap[i] (даже почти наверняка не лежит). Это верно только для корня. Попробуйте выводить массив heap на каком-нибудь примере из хотя бы 5-10 операций после каждого добавления и почти наверняка на первом же случайном тесте будет видно, что это не так. Ну и соответственно удалять так тоже не получится.