3

最大ヒープ (配列で表されると仮定) では、ヒープの一番上 (つまり、ヒープ内の最大値) が配列内の最後の要素 (つまり、ヒープ内の最小値の 1 つ) と入れ替わります。最後の要素が削除され、新しいヒープの最上位要素が他の値と交換されて、適切な場所に戻ります。

代わりに、一番上の要素が削除されず、他の要素がヒープを「埋める」ことができるのはなぜですか?

4

4 に答える 4

6

ヒープの重要な特性の 1 つは、基礎となるバイナリ ツリーが完全なバイナリ ツリーであることです (つまり、最後のレベルを除くすべてのレベルが完全に「埋められる」必要があります)。これは、各レベルO(lg N)で 1 つの要素を変更するだけでよいため、ヒープが操作できるようにするためです。O(lg N)例を見てみましょう

    10
   /  \
  8    7
 / \  / \
5  6  4  3

あなたの方法に従って、取得したヒープを「埋める」と

     8
   /   \
  6     7
 / \   / \
5  ?   4  3

に「穴」があるため、ツリーは完全なバイナリ ツリーではなくなりました?。木が完成していることがわからないため、木の高さについては何もわからないため、O(lg N)動作を保証することはできません。

これが、完全なバイナリ ツリー プロパティを維持するために、ヒープの最後の要素を取り、それを一番上に置いてから下にシャッフルする理由です。

于 2012-07-14T23:52:32.420 に答える
4

一番上の要素が削除されず、他の要素がヒープを「埋める」ことができるのはなぜですか?

これは、要素のインデックスがヒープの構造を維持する上で重要な役割を果たすためです。index の要素の 2 つの子は、indexとiに配置されます。最上位の要素を「単に削除」した場合、要素が存在しなくなるため、インデックスと要素の子が含まれなくなり、別のヒープが作成されることはありません。ある意味では、適切に機能するヒープではなく、2 つの「壊れた」ヒープが作成されることになります。インデックス 0 の値を置き換える必要があります。そうしないと、残りの要素間のインデックス スキームが壊れてしまいます。2*i+12*i+212maxmax

一番上の要素を削除しても気付かれないことはありませんが、一番下の要素を削除しても問題ありません。必要なのは、最小の要素が ではlast-1なく にあることに注意することだけですlast。したがって、一連の操作は次のようになります。

  • 安全に外せる要素を外す
  • 安全に取り外すことができない要素の代わりに置きます
  • 各ステップで 2 つの親のうち高い方を選択して、要素が落ち着くまでヒープに浸透させます。
于 2012-07-14T23:59:45.967 に答える
2

概念的には、あなたが提案するものはうまくいくでしょう。ヒープの抽象的な定義により、最上位の要素を削除して、他の要素を「ふるいにかける」ことができます。

実際には、一般的なヒープの実装では、連続するポインターの配列を使用してツリーをシミュレートします (要素nの親が位置n/2にある場合)。この実装では、ポインターの配列に「穴」を残すのは不便です。

その問題を解決するための「トリック」は、最後の要素をスワップインし、「ふるい分け」ステップで再配置することです。これにより、連続するすべての配列要素がツリーの一部であり、シーケンスに穴がないことが保証されます。これにより、アルゴリズムの実装が容易になり、リンク フィールドに必要なスペースを節約できます。

エグゼクティブ サマリー: これは単なる実装の詳細です (非常に便利で非常に一般的です)。

于 2012-07-14T23:53:09.920 に答える
1

ヒープアルゴリズムの全体的な考え方は、常に要素の完全なツリー（配列で表される）を維持することです。ツリーのルートから何かを削除した場合は、代わりに他の何かをそこに配置する必要があります。配列でそれを達成する最も効率的な方法は、最後の要素をそこに移動することです。

あなたの懸念は、配列の最後の要素（ツリーのリーフ要素）が最小の要素であるという仮定に基づいているようです。それは正しくありません。ヒープ配列は完全にソートされていません。ヒープには、各サブツリーに「垂直」の順序がありますが、サブツリー間に「水平」の順序はありません。配列の最後の要素は、ルートからそのリーフまでの一意のパスで確かに最小になりますが、通常、ヒープ全体で最小になるわけではありません。

サイズのヒープのリーフ要素を見ると、それはヒープ全体の中で最も優れNた要素の1つではないと確かに言えます。しかし、あなたが言えるのはそれだけです。たとえば、ツリーに256個の要素がある場合、配列の最後の要素（またはその他のリーフ要素）は9番目から256番目の間のどこかにランク付けされます。見る？256のうち9番目かもしれません！「最小」などの要素を参照することは、単にばかげています。平均して、それは最小ではないだけでなく、最小に近くさえありません。log N

繰り返しになりますが、最後の要素は、連続配列を維持するための最も安価な方法であるため、特に選択されています。配列ではなくリンクされたツリーなど、他の方法でヒープを実装した場合、ルートの削除後にヒープを復元する最適な方法は異なる場合があります。

于 2012-07-14T23:50:21.093 に答える