0

ここに、バイナリヒープの配列実装のスニペットがあります。このforループが擬似コードで何を意味するのかを理解するのに助けが必要です。

public void insert (Anytype x) { 
    int hole = ++currentSize; //currentSize is the size of the array
    for (array[0] = x; x.compareTO(array[hole / 2]) < 0; hole /= 2)
        array[hole] = array[hole / 2];
    array[hole] = x;
}

このforループがどのように機能するのか理解できないようです。ありがとうございました。

編集は穴を埋めました

4

2 に答える 2

1

バイナリヒープに変換された配列は、次のように表示されます。

         [elem 0] <-- put the inserted element here? (why? a precaution perhaps?)

         [element 1]...
    [element2] [ element3 ]  
[elem4][elem5] [elem6][elem7]  
[x][x] [x][x]  [x][XX] ... <-- unoccupied

コードは、インデックスホールを2で割ることにより、各ノードの親に移動します。次に、親>現在のノードの場合、親を現在のノードに移動します。

私が思うに間違いがあります...少なくともこれは典型的な解決策ではありません。挿入された要素を最後の非占有の「穴」として配置し、その位置から上に移動します...。

正しい方法は、最後の要素の親の比較を開始し、ルートに向かって反復することです。交換する必要はありませんが、インデックス「hole」が終了する場合は常に、それが新しい要素を最終的に配置するための適切な場所です。（通常のソリューションでは、「X」を最後の位置に配置してスワップしますが、これは非効率的です。）また、forループの最初の初期化は不要です。

とにかく、インデックス0が省略されている場合、インデックス演算は機能します。

于 2012-10-25T07:10:08.307 に答える
0

何を探しているのかよくわかりませんが、次のようになります。

compareToはintを返します。x.compareTo（y）は、xがyより小さい場合、負の数を返します。

したがって、コードは大まかにこれを行います：

for( set the first pos in the array to x; if x is less than array[hole/2]; hole/=2){
   array[hole] = array[hole/2];

Set your arr[final val of hole] to x
于 2012-10-25T07:10:38.760 に答える