フィボナッチヒープの設計と解析に関する質問

Question

フィボナッチヒープは、CLRSが の仕組みを理解するための本当に良い試みをしたにもかかわらず、分かりにくいことを証明しています。しかし、いくつかの質問 は私には本当に不明確である：

• なぜあなたは、T + 2mのようなポテンシャル関数を選ぶのでしょうか？推論は何ですか？
• ノードのマーキングの理由は何ですか？ ノードをルートリストなどに置くと便利ですが、なぜこのようなスキームが思い浮かぶでしょうか？

ありがとう！

Answer 1

潜在的な機能を選択する理由は、さまざまな要因の組み合わせに関係します。典型的には、電位はt + 2mとして選択され、ここで、tはツリーの数であり、mはマークされたノードの数である。これらの部分を別々に分析することができます。

最初に、潜在的な関数にはt項が含まれています。これは、delete-minステップがリンクリストの異なるツリーを繰り返しマージすることによって機能するためです。これを行うために必要な時間はそこにある木の数に依存し、各反復は木の数をおおよそO（log n）の数に減らします.nはヒープ内のノードの数です。潜在的な関数にt項を含めることによって、すべてのツリーを折りたたむために行われた作業を、最初にツリーをこのリストに追加した初期の操作にバックチャージすることができます。

潜在的な関数には、同様の理由で2mの項が含まれています。 reduce-keyを呼び出すと、親からノードを切り取り、親に印を付けます。親が既にマークされている場合は、親をマークします。ここで行われる作業の量は、ノードを切断しているときのパスの長さに比例しますが、ノードのすべてのマークが解除されます。したがって、マークされたノードの数を考慮した潜在的な機能がある場合、1回の長い一連のカットが高価な場合がありますが、その作業を以前の作業にバックチャージしてより均等に分散することができます。この用語がmではなく2mであるのは、切断されたノードの数を減らすことで潜在的可能性を低下させるため、リンクされたリストにツリーを追加することによって潜在能力を高めているからです。マークされたノードの各ドロップがポテンシャルを2つ減少させると言うと、カットからの潜在的なネットの低下は-1であるため、将来のマージ・ステップをこの減少に課すことができます。

私たちがなぜマーキングを行うのかは、フィボナッチヒープに残っている木の数とサイズを決定する際に、数学が正しく働くことです。最初はフィボナッチヒープを思いつくために必要な本物の天才的ステップであったと主張することができます。基本的に、各ツリーからあまりにも多くの子を切り取ることができれば、ヒープはバランスを失います。十分にカットできなければ、減らしキーを効率的に実装できません。 「あなたは1人の子供を失うことができる」と言うバランスを見つけることは良い妥協であり、結果として得られる数学は非常にきれいになります。

希望すると便利です。