問題
insert、meld、find-min、extract-min、decrease-key、deleteをサポートするフィボナッチヒープを実装してください。ルートリスト、親子リンク、次数（degree）、マークビット、カスケードカットがどのように連携して機能するかを説明し、ポテンシャル関数を使用して、insert、meld、find-min、decrease-keyがならしO(1)であり、extract-minがならしO(log n)である理由を示してください。
面接官がテストしていること
- すべてのならしO(1)操作が常にO(1)であると述べるのではなく、実際のコストとならしコストを区別できているか。
- 双方向循環リスト、最小値ルートポインタ、ノードハンドル、親ポインタを正しく維持管理できるか。
- decrease-keyがカット、マーキング、カスケードカットを正しく実行しているか。
- 理論上の優位性、エンジニアリングにおける定数倍のオーバーヘッド、ペアリングヒープや二分ヒープとのトレードオフを説明できるか。
模範解答
フィボナッチヒープは、ヒープ順序を満たす木の集合です。ルートは双方向循環リストを形成し、各ノードは親、子リスト、次数、マークビットを保持します。この構造では、次数ごとにルートが結合されるextract-minの実行時まで、統合作業（consolidation）を遅延させます。
insertはノードをルートリストに追加して最小値を更新します。meldは2つのルートリストを結合します。decrease-keyによってヒープ順序が崩れた場合、そのノードを親からカットしてルートリストに追加します。親がすでに子を1つ失っている場合は、再帰的にカスケードカットを実行します。マークは、ノードがすでに子を1つ失っているかどうかを記録し、カスケードによる影響を制限します。
extract-minは最小値ルートの子をルートリストに昇格させ、そのルートを削除し、同じ次数を持つルートを繰り返し結合します。一般的なポテンシャルは、ルートの数にマークされたノードの数の2倍を加えた値です。insertとmeldはルートを増やしますが、定数コストしか支払いません。カスケードカットはマークされたノードを減らし、そのコストはポテンシャルによって支払われます。ヒープ順序によって最大次数が制限されているため、extract-minでの結合回数はO(log n)に抑えられます。
実装のスケッチ
以下の擬似コードは重要なdecrease-keyの処理フローを示しています。ノードハンドルは呼び出し元が保持します。
decreaseKey(x, newKey):
if newKey > x.key: error
x.key = newKey
p = x.parent
if p is not empty and x.key < p.key:
cut(x, p)
cascadingCut(p)
if x.key < min.key:
min = x
cut(x, p):
removeFromChildList(p, x)
p.degree -= 1
addToRootList(x)
x.parent = empty
x.mark = false
cascadingCut(y):
p = y.parent
if p is empty: return
if y.mark is false:
y.mark = true
else:
cut(y, p)
cascadingCut(p)extract-minの実行中は、最小値ルートを削除する前に子を昇格させながら、nextポインタを安全に退避させてください。同じ次数のルートを結合する際は、親、子、次数、マークを更新し、その後に新しい最小値を走査して見つける必要があります。
よくある落とし穴
- 配列ベースの二分ヒープを書いて、それがフィボナッチヒープのならしO(1)のdecrease-keyを持つと主張してしまう。
- カット後に親ポインタやマークのクリアを忘れ、次のカスケードを破損させてしまう。
- 無効なnextポインタを使用しながら、双方向循環リストからの削除を行ってしまう。
- extract-min後に古いルートのみを比較し、ルートリストに昇格した子ノードや最小値スキャンを見落としてしまう。
- ポインタの追跡、キャッシュ局所性、メモリアロケーション、実装の複雑さを無視して、漸近的限界値（O表記）のみを比較してしまう。
計算量のトレードオフ
decrease-keyが頻繁に発生し、meldが必要で、ならし解析が許容される場合、フィボナッチヒープは魅力的な理論的限界値を持ちます。代表的な例として、プリム法やダイクストラ法の計算量改善が挙げられます。本番環境では、ペアリングヒープ、ランク・ペアリングヒープ、二分ヒープの方がシンプルでキャッシュ効率が高いため、より競争力がある場合が多々あります。
これらの計算量はノードハンドルを保持していることを前提としています。呼び出し元がキーによってのみノードを検索できる場合、補助インデックスが必要となり設計が変わります。並行実装では、ルートリストとハンドルの所有権も定義する必要があります。ロックフリーの安全性はならし解析から自動的に得られるものではありません。
単一要素、重複キー、空のヒープとのmeld、連続するdecrease-key、最後のノードの削除などをテストしてください。ランダムな操作シーケンスを生成し、最小値とextract-minの順序を基準となる優先度付きキューと比較します。ノードが連続して2つの子を失う状況を構築し、1回目の喪失でマークされ、2回目の喪失でカットされることを確認してください。
参考文献
- MIT OpenCourseWare Fibonacci heaps 講義：ポテンシャル解析と decrease-key / extract-min の計算量。
- Fibonacci Heaps Revisited：カスケードカットとならし計算量の再検証。
- Fredman と Tarjan の原著論文：Fibonacci heaps and their use in network optimization algorithms。
関連する質問
マークされたノードがポテンシャルに2ユニット寄与するのはなぜですか？
カスケードカットは、マークされたノードを1つ削除し、ルートを1つ追加します。2ユニットのポテンシャルにより、マークのクリアとルートの追加のコストが賄われるため、カスケード全体のならしコストが定数に保たれます。
extract-minがならしO(log n)であるのはなぜですか？
最小値を削除してその子を昇格させた後、統合作業によって次数ごとに最大1つのルートのみが残されます。ヒープ順序によりノードの次数はその部分木のサイズに結びつけられているため、最大次数はO(log n)となり、結合回数が制限されます。
meldがならしO(1)で可能なのはなぜですか？
2つの循環ルートリストを直接連結し、それらの最小値ポインタを比較するだけで済むためです。同じ次数の木の統合は、その後のextract-minまで行われません。
二分ヒープの方が適しているのはどのような場合ですか？
decrease-keyの頻度が低い場合、配列の局所性が重要な場合、ノードハンドルの管理が不便な場合、またはチームがシンプルな実装を重視する場合には、二分ヒープを使用します。二分ヒープは予測可能なメモリ挙動でO(log n)の操作を提供します。
deleteはどのように実装しますか？
ノードのキーを負の無限大に減らし、extract-minを呼び出します。本番環境の実装では、有効なビジネスキーが番兵と誤認されないよう、キーのドメイン、番兵の動作、ハンドルの無効化を適切に定義する必要があります。