【ふぃぼなっちひーぷ】
フィボナッチヒープ とは？
最終更新:
💡 仕事をまとめ、操作列全体の費用を抑えるヒープ
複数の木を管理し、挿入とキー減少を償却O(1)、最小要素の取り出しを償却O(log n)で行う優先度付きキューの実装。操作列全体の費用を評価する償却解析と、1回の最悪時間を区別することが大切です。
📌 このページのポイント
ひよこ フィボナッチヒープは何が得意？
ペンギン先生 挿入と、すでにある要素のキーを小さくする操作を償却O(1)で行えることだよ。複数の木を管理し、必要な整理を最小要素の取り出しなどへまとめる。すべての操作がO(1)ではなく、最小要素を取り出す操作は償却O(log n)なんだ。
ひよこ 償却って平均のこと？
ペンギン先生 操作列の総費用をまとめて評価する方法だよ。ランダムな入力の平均を取る平均ケース解析とは違う。たとえばキー減少の1回で連鎖的な切り離しが起きても、操作列全体では費用を抑えられると示すんだ。1回ごとの応答時間の保証とも区別しよう。
ひよこ 木をどう整理するの？
ペンギン先生 親のキーが子以下というヒープ順序を守る。最小要素を取り出した後は、根の子の数が同じ木を結合して整理する。キー減少で親との順序が壊れたら木を切り離し、条件に応じて親側でも切り離しを続けるよ。
ひよこ グラフではどう役立つ？
ペンギン先生 ひよこ いつもこれを選べばよい？
ペンギン先生 計算量は大切だけれど、ポインター操作や管理情報、実装の複雑さもある。扱うデータと操作の割合、必要な応答時間を考え、より単純なバイナリヒープなどと測定して比較しよう。理論上の上界と、実際の所要時間は別なんだ。
もっと詳しく知りたい人へ
図の根どうしにも親子関係がある？
ありません。根の集合を管理するリストと、木の親子関係は別です。実装では根や子を循環する双方向リストで管理する方式が使われますが、図は親子関係だけを線で示しています。
まとめ：ざっくりこれだけ覚えればOK！
「フィボナッチヒープ」って出てきたら「挿入やキーの減少を効率よく扱う優先度付きキューの構造」と思えばだいたいOK！
📖 おまけ：英語の意味
「Fibonacci Heap」 ＝ フィボナッチヒープ
💬 子の数に対する部分木の最小サイズの解析に、フィボナッチ数が現れます。子の数そのものが常にフィボナッチ数になるという意味ではありません。