Fibonacci Heap

個人的メモ

具体的には binomial heap(二項ヒープ) の改良版で binomial heap では push, union 時に厳密に二項ヒープの条件 "次数 $k$ の二項木は次数 $0 \sim k-1$ の二項木を子として持つ", "同じ次数の二項木は高々 $1$ つ" という条件を常に満たしていたため, 各クエリの最悪計算量が $\O (\log n)$ であったが, fibonacci heap では厳密に条件を満たしたヒープの構築を delete_min クエリに遅延処理をすることで delete_min のみならし $\O (\log n)$ 時間で push, union, decrease key などをならし $\O (1)$ 時間で行うことができる.
push, delete_min クエリのみの場合は単に push クエリ時の処理が delete_min 時に遅延処理されるだけなので delete_min 操作の終了時には二項ヒープになるが, decrease_key クエリによってヒープ木内の任意の頂点についてその頂点を根とする部分木が脱離する可能性がでてくるため二項ヒープの条件は崩れる. ここでむやみやたらに部分木の脱離を許すのではなく, 根を除く頂点について子が脱離する回数を高々 $1$ 回と制限すると木の根の次数が頂点数の $\log$ で抑えることができる. このときに根の次数が $k$ となるような木でありうる最小の頂点数が $k$ についてフィボナッチ数列(二項ヒープの場合は $2$ べき)を成し, これが名前の由来だと思う.
(上記の参考スライドの補足)
ポテンシャルを $tree(H) + 2 \times marks(H)$ と取っているイメージは木の根の頂点については後にマージされる際にかかる計算量の分の $1$, マークされている頂点については後に部分木として離脱し, 新たに木の根になるのにかかる計算量の分に $1$, そして木の根になった後に同じくマージされる際にかかる計算量の分に $1$ の合計 $2$ がかかっていると見ることができる.
一般的なならし計算量の解析と同様にならしコストは (実際にかかるコスト) + (ポテンシャルの差分) で計算され, ポテンシャルが増えることは後の計算のために貯金すること, 減ることは貯金していた分を使うことに対応している.

(fibonacci heap 以降のヒープの(雑な)話)
fibonacci heap における push, delete_min, decrease_key にかかる各ならし計算量を最悪計算量で実現するヒープとして relaxed heap がある([Driscoll, Gabow, Sharairman, Tarjan 1988]). このヒープはその名の通りヒープの条件を緩めたもので子の要素は親の要素より小さくないという条件を満たさないノードを $\log n$ 個くらい許すことにして更新をする. ただ find_min には $\O (\log n)$ 時間がかかるのと merge もならし $\O (\log n)$ かかる. 一応 [Brodal 1996] で削除以外の操作がすべて最悪定数時間, 削除は最悪 $\O (\log n)$ 時間を達成する comparison based のヒープが紹介されていて漸近的に最適である(ただかなりややこしそう).
他にもヒープ操作にかかる計算量の情報理論的下界を下回る計算量を実現したものとして soft heap がある([chazelle 2000]). こちらはヒープ内の key の値を途中で変化させることで保持する要素の情報量を落としさらなる高速化を測るもので, 厳密にはヒープではないし, もっというと relaxed heap と違い insert や delete_min クエリを正しく処理することはできない. ただ key の値をある程度恣意的に変化させて良いという条件の下で delete, findmin などのクエリを $\O (1)$ で処理でき, さらに insert された要素の個数を $n$ としたときパラメーター $\epsilon$ について, insert にかかる計算量が $\O (\log (1 / \epsilon) )$, かつヒープ内の変更された key の値は高々 $\epsilon n$ 個のようにパラメタライズされる.
ここで comparison based model において sort にかかる時間計算量は決定木を用いた証明から $\Omega(n \log n)$ であることを思い出すと, $n$ 回のヒープ操作にかかる計算量は $\Omega (n \log n)$ である. つまり soft heap はヒープの操作にかかる計算量の情報理論的下界を下回る計算量を達成していることが分かる(繰り返しになるが soft heap は厳密にはヒープではないし, insert や delete_min クエリを正しく処理することはできない.).
この soft heap は種々のアルゴリズムに応用されていて例えば最小全域木を最悪計算量 $\O(m \alpha(m, n))$ で求めるアルゴリズムなどに使われている(fibonacci heap では prim 法を用いて $\O (n \log n + m)$ time とか $\O (m \log^* n)$ time とかが限界だった). 論文を読んでいないのでどういう風に用いるかは知らない...(一応 wikipedia の記事 の Application には soft heap を selection algorithm に応用する例が載っている.)