Как известно, обычная реализация кучи не поддерживает удаление произвольного элемента по его значению. Конечно, проблема решается стандартным методом: завести хеш-таблицу и для каждого элемента кучи поддерживать указатель на его место. Не самый оптимальный по скорости написания метод. Существует другой подход, на мой взгляд, более удобный. Тем более у нас уже есть реализация кучи, и это нужно использовать.

Пусть $$$H$$$ — куча с которой мы хотим работать. Создадим новую кучу $$$Del$$$, В которую будем складывать "удаляемые элементы". То есть, когда пришёл запрос на удаление $$$x$$$, с исходной кучей ничего не происходит, мы просто берём $$$x$$$ и добавляем его в $$$Del$$$. (Для простоты я пока что считаю, что все запросы корректны, то есть удаляемый элемент гарантированно есть в $$$H$$$).

При обращении к максимальному элементу может так случиться, что он уже был удалён, поэтому надо восстановить нашу кучу. А именно, пока элементы на вершине $$$Del$$$ и $$$H$$$ совпадают — извлекаем их обоих и повторяем процедуру.

Все операции с кучами требуют $$$\mathcal{O}(\log n)$$$ времени, где $$$n$$$ — количество добавляемых/удаляемых элементов, при этом каждый из них только один раз попадает в $$$H$$$, один раз в $$$Del$$$, а также по одному разу извлекается из куч. Значит суммарное время работы $$$\mathcal{O}(n \log n)$$$.

Теперь к более важному вопросу: почему это вообще работает?

Пусть $$$m$$$ — максимальный элемент в $$$H$$$ (куча на максимум). Тогда возможны две ситуации:

1. $$$m$$$ был когда-то раньше удалён, а значит $$$m$$$ лежит в $$$Del$$$. Но так как некорректных запросов у нас пока что нет, можно утверждать, что $$$m$$$ является максимальным элементом $$$Del$$$ тоже. Алгоритм извлекает его из обеих куч и переходит к следующему максимуму.
2. $$$m$$$ не был удалён. При этом, если $$$m$$$ лежит в корне $$$H$$$, то максимум $$$Del$$$ точно меньше $$$m$$$, так как все большие уже были удалены.

Например, $$$H = [9, 6, 3, 1, 5, 2]$$$. Мы получили 3 запроса на удаление: $$$1$$$, $$$9$$$ и $$$3$$$, которые успешно положили в $$$Del$$$. То есть $$$Del = [9, 3, 1]$$$. Пытаемся извлечь элемент и ожидаем увидеть $$$6$$$ на выходе, но сейчас в корне лежит $$$9$$$ — нужно запустить процедуру восстановления кучи. Корни совпадают, а значит извлекаем их:

Теперь всё хорошо, и, как и хотели, получаем $$$6$$$. Следующий запрос извлечения не изменит вторую кучу:

Теперь опять вершины совпадают, а значит чиним кучу:

Всё отлично работает. Однако будет интереснее, если разрешить запросы, при которых элемента в куче может и не существовать. Очевидно, что текущая реализация не годится. Например, у нас была куча $$$H = [3, 2, 1]$$$ и $$$Del = []$$$. Получаем запрос на удаление $$$4$$$, и, как и полагается, кладём её в $$$Del$$$

Далее пусть идёт запрос на добавление $$$4$$$:

Теперь извлечение максимума вернёт $$$3$$$, хотя правильный ответ, конечно, $$$4$$$.

Видно, что действия по удалению должны зависеть от времени прихода элемента в кучу. Так и сделаем: вместе со значением будем хранить время добавления (в случае $$$Del$$$ — удаления) элемента из кучи. Под временем я подразумеваю количество операций, которые уже были совершены над кучей. При таком определении, например, не возникает ситуации, когда времена двух разных действий равны.

Пусть $$$m$$$ — максимальный элемент в $$$H$$$, $$$d$$$ — максимальный в $$$Del$$$ ($$$m.time$$$ и $$$d.time$$$ — времена добавления/удаления соответственно). Разберём случаи:

1. $$$m > d$$$ — Всё хорошо, возвращаем $$$m$$$.
2. $$$m < d$$$ — Очевидно, что $$$d$$$ был добавлен некорректным запросом, извлекаем его.
3. $$$m = d$$$ — Если $$$m$$$ был добавлен в $$$H$$$ раньше, чем его удалили, то есть $$$m.time < d.time$$$, то извлекаем оба. Иначе $$$m$$$ удалили раньше добавления, а такого быть не может, поэтому извлекаем только $$$d$$$.

Повторяем проверки до тех пор, пока не сможем вернуть ответ, попав в $$$1$$$ случай.

Конечно есть std::set, и он, хоть и менее эффективно, но справляется с описанной задачей, позволяя параллельно делать ещё много других вещей. Поэтому эта статья ни в коем случае не претендует на практическую полезность, а скорее описывает красивое расширение кучи, которое может быть интересно в образовательных целях.

Так что не судите строго)