フィボナッチヒープ

計算量（最大ヒープ）

操作	最悪計算量	償却計算量
最大値の取得	O(1)	O(1)
要素数の取得	O(1)	O(1)
追加	O(1)	O(1)
削除	Ω(n)	O(log n)
値の更新	Ω(n)	O(1)

上記の償却計算量を最悪計算量にしたい場合は、弛緩ヒープ (英: relaxed heap) を用いると良い^[1]。

フィボナッチヒープはminimum-heap propertyを満足する木の集まりである。つまり、ある子のキーは常に親のキーよりも等しいか大きい。つまり最小のキーは常に何れかの木のルートにある。二項ヒープと比較してフィボナッチヒープの構造はより柔軟である。木は規定された形を特に持っておらず、極端な場合はヒープ中の n 個の要素が全て別々の（n 個の）木に属しているかもしれないし、深さ n の一つの木に属しているかもしれない。この柔軟さによって、ある種の操作を後回しにするなど「怠惰な」処理方法が許される。例えば、二つのヒープを結合するには単に二つのヒープの木のリストを連結するだけで良いし、「キーの減算」操作の過程ではあるノードが親から切り離されて新しい木を作る場合がある。

しかしながら、処理時間を抑えるためには、何らかの時点でヒープにある種の秩序を導入しなければならない。特に、ノードの次数(＝ノードが直接持つ子の数)はかなり小さく抑えられる：個々のノードの次数はたかだか O(log n) であり、かつ、次数 k のノードが持つサブツリーの大きさは少なくとも Fk + 2 である（ここで Fk は k 番目のフィボナッチ数）。これを守るために、ルートでないノードからはたかだか一つの子しか切り取れないという規約を作る。二つ目の子を切り取る場合は、そのノード自身も親から切り取って新しい木のルートにする。木全体の数は「最小値の削除」操作によって木同士を繋ぐことで減少する。

柔軟な構造を持つために、一部の操作には長い時間がかかる一方、他の操作は非常に速く終わるということが起きる。走行時間の償却解析においては、「非常に速い操作」の所要時間は実際の所要時間よりも若干長いものとして扱う。この余分な時間は、後に「遅い操作」が実際に要した時間から差し引かれる。後で使うために取っておかれている時間の量は、任意の時点でポテンシャル関数によって計測される。フィボナッチヒープのポテンシャル関数は次式によって与えられる。

${\displaystyle Potential=t+2m}$

ここで t はフィボナッチヒープの中にある木の数、m はマークされたノードの数である。あるノードは、自身が他のノードの子となって以降、自身の子が少なくとも一つ切り取られたならばマークされる（但しルートはマークせず、マークされたノードがルートになった場合はマークを消す）。

従って、ヒープ内のそれぞれの木のルートは 1 単位時間を保持している。この単位時間は後でこの木を他の木と償却時間 0 でリンクするのに使うことができる。また、個々のマークされたノードは 2 単位時間を保持している。このうち 1 単位時間はそのノードを親から切り離すのに使うことができる。もしこれが起きると、そのノードはルートとなり、残る 2 つめの単位時間を他のルートと同様に保持し続けることになる。

高速に実装および結合を行うには、すべての木のルートノードを環状にリンクし、双方向リストにする。それぞれのノードの子もまた同様なリストにする。それぞれのノードには子の番号とノードにマークがついているかどうかを維持する。さらに最小のキーを含むルートへのポインタも維持する。

最小値検索の操作は、最小値を含むノードへのポインタを維持しているなら些細なものである。ポインタの維持にはヒープのポテンシャルを変更することはないので、実時間および償却時間は共に一定である。上記のために、結合操作は二つのヒープの木のルートのリストを単純につなぎ合わせることで実装される。この操作は一定時間で処理可能でありまたヒープのポテンシャルも変更しない。また償却時間も一定であることも導かれる。挿入操作は一つの要素を持つ新しいヒープを作りそれを結合すればよい。この操作にかかる時間は一定であり、ポテンシャルは木の数が増えることにより一つ増える。償却時間はまだ一定である。

最小値拡大操作(最小値削除)は3つのフェーズに分けて行われる。最初に最小要素を含むルートノードを取り出しそれを削除する。ルートノードの子は新しい木のルートになる。もしその子の数がdならば、すべての新しいルートノードの処理にかかる時間は O(d) でありポテンシャルはd-1増える。それゆえにこのフェーズの償却時間は O(d)=O(log n) になる。

しかしながら最小値拡大操作を完了するには、最小値を持つルートノードへのポインタを更新する必要がある。不幸にもn個までのルートノードをチェックする必要があるかもしれない。二番目のフェーズでは、同じ次数のルートノードを一緒につなげてルートノードの数を減らす。uとvという二つの同じ次数のルートノードがあった場合、一方を子にしてよりキー値が小さいもう一方をルートのままにしておく。そのルートの次数は一つ増える。この操作をすべてのルートが異なる次数になるまで繰り返し行う。同じ次数の木を効率的に検索するために、O(log n) の長さを持つ配列を用意し、それぞれの深さのあるルートへのポインタを保持するようにする。2番目に同じ深さのルートが見つかったならば、その二つの木を結合して配列の内蔵を更新する。二番目のフェーズ開始時のルートの数がmとすると、実実行時間は O(log n + m) になる。最後に、高々 O(log n) 個のルートになる(それぞれのルートは異なる次数になっている)。それゆえにポテンシャルは少なくとも m - O(log n) 減り償却時間は O(log n) になる。

3番目のフェーズではルートとして残っているものをチェックして最小値を検索する。これには O(log n) の時間がかかりポテンシャルは変化しない。最小値拡大操作の全体の償却時間は O(log n) になる。

あるノードについてキー値減算操作を行うということは、つまりキーを減算しその結果ヒーププロパティに違反することになったら（新しいキーが親のキーよりも小さくなる）そのノードを親から切り離すことである。もし親がルートノードでなければ、そのノードにはマークがつけられる。もしすでにマークがつけられていたならばそのノードを切り離して親にマークをつける。それをルートかマークされていない頂点に到達するまで上に向かって続ける。この処理中にいくつかの、ここではkとする、新しい木を作成する。これらの新しい木は恐らく最初の一つを除いてもともとマークされていたが、ルートになるのでマークされなくなる。一つのノードはマークされうる。それゆえにポテンシャルは少なくともk - 2減る。切り取るのにかかる実時間は O(k) かかる。それゆえに償却時間は一定である。

最後に削除操作は、単に削除する要素のキーを無限に減らす、つまりヒープ全体の中で削除対象の要素のキーを最小にするというように実装される。これをノードを削除するための最小拡大と呼ぶ。この操作にかかる償却時間は O(log n) である。