Операция Delete-Max в куче min-max

Question

Я реализую кучу min-max, тип очереди с двусторонним приоритетом. Вы можете посмотреть здесь для получения дополнительной информации о кучах min-max.

Код для операций вставки и удаления мин прост и доступен в сети. Но я также пытаюсь реализовать операцию delete-max в куче min-max.

Первоначально я чувствовал, что delete-max в куче min-max будет таким же, как delete-max в куче max-min (если мы рассмотрим поддерево кучи min-max, содержащее элемент max, это напоминает кучу max-min). Таким образом, реализация будет простой и аналогичной delete-min кучи min-max.

Но есть проблема:

Как видно из рисунка выше, хотя элемент max равен 70, последний элемент (12) кучи min-max не находится в поддереве, содержащем 70. Итак, я могу использовать его для замены пробела, оставленного в левом поддереве после удаления 70?

Если мы не используем этот элемент и вместо этого следуем процедуре delete-max кучи max-min и используем 20, чтобы заменить пробел, следующий элемент, вставленный в кучу, будет иметь правильный дочерний элемент, равный 10, и навсегда не будет правильного дочернего элемента. из 9

Итак, кто-нибудь может мне помочь?

Answer 1

Я считаю, что правильно удалить самый правый узел на последнем уровне и использовать его для замены удаленного элемента max, даже если он пересекается в дереве. Обоснование следующее:

1. Удаление самого правого узла на последнем уровне не изменяет ни одного из инвариантов, которые необходимо хранить для каких-либо узлов в этом дереве: все узлы на минимальных уровнях все еще меньше, чем все их потомки, и все узлы на максимальных уровнях все еще больше, чем их потомки.

2. Дерево все еще является полным двоичным деревом.

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

Надеюсь это поможет!