1

フィボナッチヒープに二項ツリーではないツリーを含めることは可能ですか? もしそうなら、これはどのように起こりますか？例を挙げていただけますか？

4

1 に答える 1

0

はい、これは発生する可能性があります。直感的には、その理由は、フィボナッチヒープでは、キーの減少操作が大きなツリーからサブツリーを切り取って機能し、（潜在的に）二項ツリーではない2つのツリーが生成されるためです。これは、キーがルートまでずっと減少したノードからバブルアップ操作を実行することによって減少キーが機能する二項ヒープとは異なります。

具体的な例を示すために、フィボナッチヒープに5つの要素、たとえば1、3、5、7、および9を挿入してみましょう。これによりヒープが得られます。

1 - 3 - 5 - 7 - 9

次に、1を抽出するdequeue-minを実行します。次に、残りのすべての要素をまとめて圧縮し、次のようにツリーをマージします。

    3
   /|
  5 7
    |
    9

ここで、キーを減らす操作を実行して、9のキーを6に減らすと仮定します。これを行うには、親から9を切り取り、それを上部のツリーのリストにマージします。

   3 - 6
  /|
 5 7

そして、ルートに3があるツリーには、3つの要素しか含まれていないため、二項ツリーではなくなりました。

お役に立てれば！

于 2012-02-13T04:30:41.980 に答える