2

私は最大ヒープを作成しようとしています。ロジックは単純です。親がその子の 1 つより小さい場合は、それらを交換します。を使って実装してみました

void maxHeapify( int i , int *a , int n ){

    int largest = i;
    int left    = ( i * 2 ) + 1;
    int right    = ( i * 2 ) + 2;

    if( left < n && a[ largest] < a[ left ])
        largest = left;
    if( right < n  && a[ largest ] < a[right])
        largest = right;
    if( largest != i ){
        swap( a[i], a[largest]);
        maxHeapify( largest , a,  n );
    }
}


int main(){
    int n;
    int * a;
    cout << "Number of elements : ";
    cin >> n ;
    a = new int[n];
    for( int i = 0; i < n ; i++){
        cin >> a[i];
    }

    for( int i = n/2 -1 ; i >= 0 ; i-- ){
        maxHeapify( i , a, n);
    }
    for(int i = 0; i < n ; i++){
        cout << a[i] << " ";
    }

    return 0;
}

入力を使用しています

2 7 26 25 19 17 1 90 3 36

木は次のように見えるはずです

        90
      36 17
   25 26 7 1
 2 3 19

そのため、配列表現は90 36 17 25 26 7 1 2 3 19 まだコードの出力である必要があります

90 36 26 25 19 17 1 7 3 2

私はそれを調べて、多くのチュートリアルで多くの同じコードを見つけました. 出力が配列内のツリーの表現ではないのはなぜですか? 私はそれを誤解しましたか？

説明ありがとう

4

2 に答える 2

0

最終的なヒープ構造は、挿入順序と初期構造によって異なります。あなたの場合、2 7 26 25 19 17 1 90 3 36空のヒープで開始し、指定された順序で要素を挿入し、各挿入後にヒープ化すると、期待する結果が得られます。

このコードにより、期待どおりの結果が得られます。

std::vector<int> b = {2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
auto it = b.begin();
while (it != b.end())
{
    std::make_heap(b.begin(), it+1);
    ++it;
}

ただし、コードが行うことは、すべての要素をヒープに事前挿入してから配置することです。これは次のようになります。

std::vector<int> b = {2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
std::make_heap(b.begin(), b.end());

どちらの結果も等しく有効です。

于 2016-10-23T23:06:31.153 に答える