5

Pairing heapを読んでいます。

とてもシンプルで、難しいのはdelete_min操作だけです。

唯一の重要な基本操作は、ヒープからの最小要素の削除です。標準的な戦略では、最初にサブヒープをペアでマージし (これは、このデータ構造にその名前を付けたステップです)、次にヒープの結果のリストを右から左にマージします。

wiki リンクにあるので、ここにコードをコピーして貼り付ける必要はないと思います。

私の質問は

  1. なぜ彼らはこの2つのパスのマージを行うのですか?

  2. なぜ最初にペアをマージするのですか? それらすべてを直接マージしませんか？

  3. また、ペアをマージした後、特に右から左にマージするのはなぜですか?

4

1 に答える 1

12

ペアリング ヒープでは、ヒープへの項目の追加は O(1) 操作です。ノードを新しいルート (現在のルートよりも小さい場合) または現在のルートの最初の子として追加するだけだからです。したがって、ペアリング ヒープを作成し、それに 0 ～ 9 の数字を順番に追加すると、次のようになります。

        0
        |
-----------------
| | | | | | | | |
9 8 7 6 5 4 3 2 1

次にdelete-minを実行すると、各子を調べて最小項目を決定し、新しいヒープを構築する必要があります。単純な左から右への結合方法を使用すると、次のツリーになります。

       1
       |
---------------
| | | | | | | |
9 8 7 6 5 4 3 2

次にdelete-minを実行するときは、残りの 8 つの子を調べる必要があります。この手法を使用すると、ヒープからすべての項目を作成してから削除するのは O(n^2) 操作になります。

ペアで結合してからペアを結合する 2 パス方式により、はるかに効率的な構造が得られます。最初のケースを考えてみましょう。最小項目を削除すると、9 つの子が残ります。それらは左から右にペアで組み合わされて生成されます。

  8  6  4  2  1
 /  /  /  /
9  7  5  3

次に、ペアを右から左に結合します。手順:

  8  6  4    1
 /  /  /    /
9  7  5    2
          /
         3

  8  6    1
 /  /    / \
9  7    2   4
       /   / 
      3   5  

  8     1
 /      |
9   ---------
    6   4   2
   /   /   /
  7   5   3

      1
      |
  ----------
  8  6  4  2
 /  /  /  /
9  7  5  3

次にdelete-minを呼び出すと、チェックするノードは 4 つだけで、次回以降は 2 つしかありません。2 パスの結合方法を使用すると、子レベルのノード数が少なくとも半分に減少します。私が示した配置は最悪のケースです。項目が昇順であった場合、最初のdelete-min操作により、ルートの下に子ノードが 2 つしかないツリーが作成されます。

これは、ペアリング ヒープの償却された複雑さの特に良い例です。insertは O(1) ですが、一連の挿入操作の後の最初のdelete-minは O(n) です。ここで、 は最後のdelete-minから挿入されたアイテムの数です。2 パス結合ルールの優れた点は、ヒープをすばやく再編成して O(n) の複雑さを軽減することです。n

この組み合わせルールでは、delete-minの償却後の複雑度は O(log n) です。厳密な左から右のルールでは、O(n) です。

于 2014-03-19T22:22:07.027 に答える