9

アルゴリズム入門の教科書でいくつかのアルゴリズムを試してみました。具体的には、バイナリヒープを100％正しく機能させようとしています。私が取り組んでいる例が正しくないことに不思議な気持ちがあり、誰かが私を正しい方向に向けるのを手伝ってくれるかどうか疑問に思いました。

与えられた配列

int[ ] arr = { 1, 2, 3, 4, 7, 8, 9, 10, 14, 16 };

MaxHeapifyから得られる結果は次のとおりです。

[ 16, 14, 9, 10, 7, 8, 3, 1, 4, 2 ]

しかし、いくつかのGoogle検索を行った後、この正確な配列を例として使用する人々は、結果が次のようになることを期待していることがわかりました。

[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]

私を混乱させているのは、MaxHeapifyメソッドが与える結果がHeapプロパティを満たしているということですが、それは予想とは異なります。以下はJavaでの私の実装です

public static void BuildMaxHeap( int[ ] arr )
{
    for( int i = (int)Math.floor( arr.length - 1 ); i >= 0; i-- )
        MaxHeapify( arr, i );
}
public static void MaxHeapify( int[ ] arr, int i )
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;

    if( left < arr.length && arr[ left ] > arr[ largest ] )
        largest = left;
    if( right < arr.length && arr[ right ] > arr[ largest ] )
        largest = right;
    if( largest != i )
    {
        int temp = arr[ i ];
        arr[ i ] = arr[ largest ];
        arr[ largest ] = temp;
        MaxHeapify( arr, largest );
    }
}
4

2 に答える 2

10

表示したヒープは両方とも有効です。心配することは何もありません。

サブノードを並べ替える方法は複数あります。

左から右にスワッピングする最も単純なケースを考えてみましょう。

   14         14
 10  9   vs  9  10
...  ...   ...  ...
于 2013-03-22T20:36:04.480 に答える
2

ヒープは有効です。これらの方法のどちらも適用しない場合、配列は必ずしもソートされないため、これらは異なります。それがヒープソートの目的です。詳細は、BuildMaxHeapで変更することをお勧めします

for( int i = (int)Math.floor( arr.length - 1 ); i >= 0; i-- )

に

for( int i = arr.length / 2; i >= 0; i-- )

私がこれを言う理由は、葉は常にmax_heapであるため、子として葉を持つ最後のノードから開始できるためです。

于 2013-03-23T02:39:23.487 に答える