algorithm - n ノードを持つフィボナッチ ヒープの高さ n を表示する方法は?

Question

n 個のノードを持つフィボナッチ ヒープの高さが n になることを示したいと思います。

例でこれを試しましたが、これを一般的に示す方法がわかりません。

Answer 1

（私はあなたが高さn-1を意味すると仮定します：nノードでは最大高さは高さn-1のリンクリストであるため、高さnは不可能です）

高さ1に到達するのは簡単です。3つのノードを追加してから、dequeue-minを実行します。これにより、1つのノードが削除され、高さが0である他の2つのノードが、高さ1のこの構造に結合されます。

A
|
B

このプロセスをもう一度繰り返して、新しいノードの1つが最低の優先度を持っていることを確認すると、これらのツリーが2つ取得され、次のようにマージされます。

A
|\
B C
  |
  D

ここで、Bに対して削除操作を実行します。これにより、Aに順序1とマークが残ります。

A*
|
C
|
D

このプロセスをもう一度繰り返して（3つのノードを挿入し、すべてが無限の負の優先度を持ち、dequeue-minを呼び出します）、これを取得します。

E
|\
F A*
  |
  C
  |
  D

Fを削除して取得します

E*
|
A*
|
C
|
D

3つのノードを追加し、1つを削除してから、残りの1つのツリーのシングルトンの子を削除するというこのプロセスを繰り返し実行すると、フィボナッチヒープを高さn-1の単一のツリーにすることができます。

お役に立てれば！