内部配列を再配置せずに最小ヒープから最大ヒープに切り替える

Question

ヒープヒープヒーププロパティを満たす要素があるとします。私は内部配列を再配置することなく、最大ヒープにヒープ分からアルゴリズムを変更した場合 は何が起こりますか？

私は配列はそのまま続ける場合、私は内部の配列に要素を追加するとき、何が起こるのか？

Answer 1

がWikipediaから、次の例を考えてみましょう：

この配列表現は次のようになります。

[1, 2, 3, 17, 19, 36, 7, 25, 100] 

今「変更」最小から最大へのヒープが、再配置なし新しい要素 "25"を挿入します。配列の位置は9になり、親ノードは位置4で "19"になります。

挿入後、新しい項目を親と繰り返し比較してヒーププロパティを保証する必要があります（現在、max-heap => parentは子）。したがって、ルートノードになるまで "25"を "19"、 "2"、 "1"にスワップする必要があります。

今のmax-ヒープ特性は、例えば、ではなく、他のノードのために、（その子は確かに小さい）ルートノードのために保持しています"3"は引き続き "7"の親であり、最大ヒープ条件に違反します。

結論：説明することは、最小ヒープを最大ヒープに変更することはありません。

Answer 2

あなたは、ヒープをネジだけでしょう。

あなたは再度heapifyする必要があります（これは時間O（N）で行うことができます）。