同じ要素を持つ最大と最小のヒープ

Question

次の例を考えてみましょう。私はminヒープに乱数を追加しています。同時に、同じヒット数で同じ数字を同じヒット数に追加しています。だから最後の2つのヒープは、同じヒット数のヒープと2つ目のヒープが同じヒット数になります。

私は最大ヒープから最大要素を削除することを決定した場合、最大ヒープからの最大の要素は常に分ヒープの一番下には以下となります。

今ここに質問ですか！もしそうでなければ、もう一つの質問は、minヒープの最後の要素をスワップしてminヒープからmax要素を削除し、最後の要素を削除したいのであれば、その要素を比較しなければならない操作を実行する必要があるでしょうか？ミニヒープを修復するために彼の子供と一緒に？それとも、親ヒープを修正するためにそれを親と比較するのはいつものケースでしょうか？

Answer 1

最大ヒープの定義により、ルートは常にその子よりも大きくなります。しかし、子供の間に特定の順序がないので、左の子供は必ずしも右の子供よりも大きくなく、逆もまた同じです。ルートである最大ヒープの最大要素は、最小ヒープ内のリーフになければなりません。どの葉が分かっているのか分かりませんが、これは要素の構成に依存します。 （つまり、これらの要素が挿入される順序は、通常、要素がツリーの左端から右端に向かって挿入されるために挿入されます）。