フィボナッチヒープ
これにはO(log n)の時間がかかりポテンシャルは変化しない。最小値拡大操作の全体の償却時間はO(log n)になる。
あるノードについてキー値減算操作を行うということは、つまりキーを減算しその結果ヒーププロパティに違反することになったら(新しいキーが親のキーよりも小さくなる)そのノードを親から切り離すことである。もし親がルートノードでなければ、そのノードにはマークがつけられる。もしすでにマークがつけられていたならばそのノードを切り離して親にマークをつける。それをルートかマークされていない頂点に到達するまで上に向かって続ける。この処理中にいくつかの、ここではkとする、新しい木を作成する。これらの新しい木は恐らく最初の一つを除いてもともとマークされていたが、ルートになるのでマークされなくなる。一つのノードはマークされうる。それゆえにポテンシャルは少なくともk - 2減る。切り取るのにかかる実時間はO(k)かかる。それゆえに償却時間は一定である。
最後に削除操作は、単に削除する要素のキーを無限に減らす、つまりヒープ全体の中で削除対象の要素のキーを最小にするというように実装される。これをノードを削除するための最小拡大と呼ぶ。この操作にかかる償却時間はO(log n)である。