0

siftdown を使用した配列 heapification - max(heap) これは 45 を 77 でスワップした結果です。次のステップに興味があります。37 を 77 でスワップするか、45 を 67 でスワップするかです。この状況が 45 を 77 でスワップしたことを考慮して、レベル 1 (レベル 0 は 37) を見ましたが、45 と 67 の状況を修正するために下に戻る必要がありますか? コンピュータの実装で最初に行われる操作はどれですか?

                            |37|  
            |77|                               |59|  
    |63|             |45|               |54|          |11|
|31|    |39|     |48|    |67|
4

1 に答える 1

0

これを行う通常の方法は、http: //en.wikipedia.org/wiki/Heapsort#Pseudocodeです。

インデックス N/2 から開始します (図では、45 を保持するスペース)。siftDOWN を実行します。(あなたの説明から、siftUP を行ったようです。) この図から始めた場合、45 をその子 (48,67) と比較し、45 と 67 を交換します。次に、インデックス (item= 63) から 1 を引きます。そこでふるい分けをします。根っこにたどり着くまで続けます。独自の子を持つノードとスワップする場合、そのノードでもふるい分けを行う必要があります。

ダイアグラムでこの順序に従うと、このパターンがツリー内のすべてのノードをチェックすることがわかります。

于 2011-05-12T06:27:43.540 に答える