最小最大ヒープでの最大操作の削除

Question

私は、最大両端ヒープを実装しています。これはダブルエンド優先順位キューの一種です。 min-maxヒープの詳細については、hereを参照してください。

挿入操作と削除操作のコードは単純でネット上で利用できます。しかし、私はまた、delete-max操作をmin-maxヒープで実装しようとしています。

最初は、max-minヒープでdelete-maxヒープと同じになると感じました（最大要素を含むmin-maxヒープのサブツリーを考えてみると、 minヒープ）。したがって、実装はmin-maxヒープのdelete-minとシンプルで類似しています。

しかし、問題がある：

70は、最大要素であり、最小 - 最大ヒープの最後の要素（12）はしていないが、上記の図に見られるように70を含むサブツリーです。したがって、70の削除後に左のサブツリーに残っているギャップを置き換えるために使用できますか？

max-minヒープのdelete-maxプロシージャを実行し、ギャップを置き換えるために20を使用すると、ヒープに挿入される次の要素は10の右の子になり、永遠に9の右の子供が存在しません。

だから誰でも助けてくれますか？

Answer 1

最後のレベルの右端のノードを削除し、ツリー内で交差しても削除されたmax要素を置き換えることは正しいと思います。より依然として小さい分レベルですべてのノード：そのツリー内の任意のノードのために保持する必要が不変のいずれかを変更しない最後のレベルの右端ノードを削除

1. ：根拠は以下でありますそれらの子孫のすべて、および最高レベルのすべてのノードは、依然として子孫よりも大きいです。

2. ツリーはまだ完全なバイナリツリーです。あなたは、このノード上に移動した後

は、あなたがして、左部分木の不変量は依然として保持することを確実にするために最大 - 最小ヒープ内の通常のフィックスアップ手順を使用することができます。

希望すると便利です。