1

ヒープのルート要素を削除するアルゴリズムを読みました。1.ルート要素をヒープの最後の要素と交換します。2.次に、ルート要素から下にヒープ化（シフトダウン）します。

他のいくつかの場所では、最後の要素の親からルートに向かって上向きに積み上げられていることがわかります（つまり、ここでdeleteTop（）関数を確認してくださいhttp://www.geeksforgeeks.org/archives/14873）したがって、正しいアプローチと混同されています：- （これは状況によって異なりますか、それとも記事自体が間違っていますか？

4

4 に答える 4

1

のコードdeleteTop()が間違っています。

この max-heap と running を指定するとdeleteTop():

        10
     8      7
    5 4    3 2
        ||
        ||
        \/ 

        2
     8     7
    5 4   3 10
        ||
        ||
        \/ 

        7
     8     2
    5 4   3 10

2<(3 and 10) であるため、結果のヒープは間違っています。

于 2012-08-09T19:19:25.477 に答える
0

他のいくつかの場所では、最後の要素の親からルートに向かって上向きにヒープしていることがわかります（つまり、ここでdeleteTop（）関数を確認して くださいhttp://www.geeksforgeeks.org/archives/14873）

のインラインコメントheapify()は、実装が中央値ストリーミング問題に適合したことを明確に示しています。ただし、一般的なヒープ構造の実装では、heapify()バブルダウンします。ヒープの実装と中央値ストリーミングの問題の詳細な説明については、このアルゴリズムの講義を参照してください。

于 2012-08-09T19:12:15.867 に答える
0

ヒープソートの概念は、最大または最小の要素を特定してヒープから削除することだと思います...どちらの方法でも実行できるため、アルゴリズムの実装が異なります。

于 2012-08-09T16:40:30.777 に答える