2

ベクトルとイテレータの基本的な理解があります。しかし、以下のコード スニペットの出力を理解する上で問題に直面しています。

具体的には、make_heap() 関数の機能を見つけることができません。出力の生成方法: 91 67 41 24 59 32 23 13 !!

私の知る限り、ヒープは次のようになります。

        91
       /  \
     67    41
    /  \  /  \
   59 24 32  23
  /
 13

したがって、出力は次のようになると予想していました: 91 67 41 59 24 32 23 13

make_heap() がどのようにそのような出力を生成したかを理解するのを手伝ってくれる人がいれば、本当に感謝しています。

int main()
{
int aI[] = { 13, 67, 32, 24, 59, 41, 23, 91 };
vector<int> v(aI, aI + 8);

make_heap( v.begin(), v.end() );

vector<int>::iterator it;
for( it = v.begin(); it != v.end(); ++it )
    cout << *it << " ";
//Output: 91  67  41  24  59  32  23  13

    return 0;
}
4

3 に答える 3

7

バイナリ ヒープは、(バイナリ ツリーであることに加えて) 2 つの制約を満たす必要があります。

  1. shape プロパティ - ツリーは完全なバイナリ ツリーです (最後のレベルを除く)
  2. ヒープ プロパティ: 各ノードはその子のそれぞれより大きいか等しい

バイナリ ヒープ内の兄弟の順序は、ヒープ プロパティによって指定されません。単一ノードの 2 つの子は、形状プロパティに違反しない限り、自由に交換できます。

したがって、あなたの例では、第 2 レベルのノード間を自由に交換して、すべて合法的な複数の出力を取得できます。

于 2013-06-27T07:48:10.857 に答える
3

ソートされていない配列をヒープ化する場合、アルゴリズムは、配列の半分がリーフ ノード (配列内のより高いインデックス) になり、残りの半分がそれらのリーフ ノードの親になるという面を利用します。アルゴリズムは、親ノードを繰り返し処理し、それらの論理サブツリーを修正するだけです。リーフ ノードは、定義上、存在しない子ノードよりも大きいため、有効なサブヒープとして開始されます。

したがって、少なくとも 1 つの非リーフ ノードを持つサブヒープのみを修正する必要があります。最後の親ノードがヒープ化されると、配列全体が有効なヒープになります。

各ステップは次のようになります。

iteration 1:

    13 67 32 24 59 41 23 91
              ^              current parent under consideration
                          ^  children of this parent

    13 67 32 91 59 41 23 24  after heapifying this sub-tree
             --          --


iteration 2:

    13 67 32 91 59 41 23 24
           ^                 current parent under consideration
                    ^  ^     children of this parent

    13 67 41 91 59 32 23 24  after heapifying this sub-tree
          --       -- 


iteration 3:

    13 67 41 91 59 32 23 24
        ^                    current parent under consideration
              ^  ^           children of this parent

    13 91 41 67 59 32 23 24  after heapifying this sub-tree
       --    --

iteration 4:

    13 91 41 67 59 32 23 24
     ^                       current parent under consideration
        ^  ^                 children of this parent

    91 13 41 67 59 32 23 24  heapify swap 1
    -- --
    91 67 41 13 59 32 23 24  heapify swap 2
       --    --
    91 67 41 24 59 32 23 13  after heapifying this sub-tree
             --          --

配列をヒープ化する単純な方法は、配列をインデックスから順にウォークスルーし、0反復n-1ごとに、そのインデックスの要素を、そのインデックスの前の要素で構成されるヒープに「追加」することです。これにより、期待したヒープが得られます。そのアルゴリズムにより、nheapify 操作が行われます。によって使用されるアルゴリズムはmake_heap()、n/2heapify 操作になります。結果は異なりますが、それでも有効なヒープになります。

于 2013-06-27T08:56:42.500 に答える