フィボナッチヒープ とは？

普通のバイナリヒープだと挿入やキーの減少にO(log n)かかるんだけど、フィボナッチヒープはこれをO(1)の償却時間でやれるんだ。やるべき仕事を後回しにして、まとめて処理する怠け者戦略なんだよ。

ポイントは「償却」計算量という考え方。1回1回の操作は遅いこともあるけど、全体を平均するとO(1)になるんだ。クレジットカードのように「今は使って後で払う」イメージだね。

実は実装がかなり複雑で、定数倍も大きいから、実際のプログラムではシンプルなバイナリヒープの方が速いことが多いんだ。でも理論的には、ダイクストラ法をO(E + V log V)に高速化できるのはフィボナッチヒープだけなんだよ。

そうなんだ。アルゴリズムの研究では計算量の理論的な上限を示すのが重要だから、フィボナッチヒープは理論計算機科学で欠かせない存在だよ。論文でよく見る「O(E + V log V)のダイクストラ法」はフィボナッチヒープ前提の話なんだ。