5

私は最小-最大ヒープを実装しています。これは両端のプライオリティ キューの一種です。min-max ヒープの詳細については、こちらを参照してください。

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

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

しかし問題がある： ここに画像の説明を入力

上の図からわかるように、最大​​要素は 70 ですが、min-max ヒープの最後の要素 (12)は、70 を含むサブツリーにはありません。したがって、それを使用して、左のサブツリーに残されたギャップを置き換えることができますか? 70の削除後？

その要素を使用せず、代わりに max-min ヒープの delete-max 手順に従い、20 を使用してギャップを置き換えると、ヒープに挿入される次の要素は 10 の右の子になり、右の子は永久になくなります。 9の。

それで、誰かが私を助けることができますか？

4

1 に答える 1

3

最後のレベルで右端のノードを削除し、それを使用して、ツリー内で交差している場合でも、削除された最大要素を置き換えるのが正しいと思います。理論的根拠は次のとおりです。

  1. 最後のレベルで右端のノードを削除しても、そのツリー内のノードを保持する必要のある不変条件は変更されません。最小レベルのすべてのノードは、すべての子孫よりも小さく、最大レベルのすべてのノードはまだ小さいです。まだ彼らの子孫よりも大きいです。

  2. ツリーはまだ完全な二分木です。

このノードを移動したら、max-minヒープで通常の修正手順を使用して、左側のサブツリーの不変条件が引き続き保持されるようにすることができます。

お役に立てれば！

于 2013-01-15T06:47:01.440 に答える