2

ボトムアップヒープ構造は、（n + 1）が2の累乗であるという事実に完全に依存していませんか？（ここで、nはノードの数です）。

たとえば、n = 21の場合を考えてみましょう。（n +1）は2の累乗ではありません。これはどのように機能しますか？

最初に挿入（n + 1）/ 2ノード、つまり11ノードを作成します。次に、（n + 1）/ 4ノードを挿入して、前に挿入したノード、つまり5.5ノードの親にします。しかし、どうすれば「ノードの半分」を挿入できますか？nが2の累乗でない場合は常に、あるレベルでノード挿入の小数に到達します。これにどのように対処しますか？

残りのノードが2の累乗になるように一定量のノードを削除し、残りのノードからツリーを構築し、完了後に削除したノードをツリーにバブリングすることを検討しました。ただし、ノードの数が多い場合、これは実行不可能になります。つまり、ノードの数= 1600です。2の最も近い累乗は1024です。つまり、576ノードをバブルする必要があり、これには比較的時間がかかります。

4

1 に答える 1

4

いいえ、これが発生する必要はありません。バイナリヒープには、最終レイヤーからノードが欠落している可能性があることに注意してください。これは、最初のステップで、最終的にヒープのコレクションになるようにノードを結合して、それらのヒープがヒープの最後の2つのレイヤーを形成することを意味します。これらのヒープのすべてが完全なヒープである必要はありません。それらのいくつかは行方不明の子供がいます。

残りのノード数が完全な2の累乗より1少ないように、除外する子の数を選択した場合は、通常どおりボトムアップ構築を続行できます。結果は完全なバイナリヒープになります。

お役に立てれば！

于 2012-07-06T00:57:28.730 に答える