MinHeapにノードを挿入する左の子に優先順位を付ける

Question

MinHeapの右にメモを挿入するコードを取得した後、ノードの左の子に優先順位を付けたい場合、どのような変更が必要なのか混乱します。ヒープを並べ替える。

I 5 //insert number 5 in the Min Heap 
I 4 
I 3 
I 2 
I 1 

、出力は次のようになります：代わりに通常の

1 2 3 4 5 

：この出力に取得する方法について

1 2 4 5 3 

任意のアイデア 入力のようなものでしょうか？前もって感謝します。

Answer 1

ヒープの構造は、アイテムを挿入する順序に完全に依存します。その理由は、挿入するときに、新しいノードをヒープの終わりに追加し、それを親のポインタを通してふるい分けることです。ルールは次のとおりです。

1. ヒープの最後に項目を追加します。
2. アイテムがその親よりも大きいか等しい場合、完了します。
3. アイテムをその親と入れ替えます。これらのルールを考える2.

から

Goが、あなたが順番[5,4,3,2,1]に項目を挿入するときに何が起こるかを歩いてみましょう。

[5] 
[5,4] // the new item is smaller than its parent, so swap 
[4,5] 
[4,5,3] // the new item is smaller than its parent, so swap 
[3,5,4] 
[3,5,4,2] // the new item is smaller than its parent, so swap 
[3,2,4,5] // still smaller than its parent 
[2,3,4,5] 
[2,3,4,5,1] // 1 is smaller than 3, so swap 
[2,1,4,5,3] // 1 is smaller than 2, so swap 
[1,2,4,5,3] 

特にバイナリヒープで特定のサブツリーを「優先度付け」する効率的な方法はありません。ヒープ内のアイテムはわずか5アイテムで十分にシンプルに見えますが、追加するすべてのレベルで兄弟ノードを適切な順序で保持するコストが増加します。ノードをソートし、結果の配列からヒープを作成する方が良いでしょう。

ソートされたヒープはあまり役に立ちません。最初の項目を削除するとすぐに、ヒープを並べ替えるとソートされなくなります。