フィボナッチヒープ
高速に実装および結合を行うには、すべての木のルートノードを環状にリンクし、双方向リストにする。それぞれのノードの子もまた同様なリストにする。それぞれのノードには子の番号とノードにマークがついているかどうかを維持する。さらに最小のキーを含むルートへのポインタも維持する。
最小値検索の操作は、最小値を含むノードへのポインタを維持しているなら些細なものである。ポインタの維持にはヒープのポテンシャルを変更することはないので、実時間および償却時間は共に一定である。上記のために、結合操作は二つのヒープの木のルートのリストを単純につなぎ合わせることで実装される。この操作は一定時間で処理可能でありまたヒープのポテンシャルも変更しない。また償却時間も一定であることも導かれる。挿入操作は一つの要素を持つ新しいヒープを作りそれを結合すればよい。この操作にかかる時間は一定であり、ポテンシャルは木の数が増えることにより一つ増える。償却時間はまだ一定である。
最小値拡大操作(最小値削除)は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番目のフェーズではルートとして残っているものをチェックして最小値を検索する。
↑ Driscoll, James R.; Gabow, Harold N.; Shrairman, Ruth; Tarjan, Robert E. (November 1988). “Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation”. Communications of the ACM. doi:10.1145/50087.50096.
上記の償却計算量を最悪計算量にしたい場合は、弛緩ヒープ (英: relaxed heap) を用いると良い。