フィボナッチヒープ
フィボナッチヒープは1984年にMichael L. Fredmanとロバート・タージャンの二人によって開発され、1987年に科学雑誌に最初に掲載された。フィボナッチヒープを導入することで、ダイクストラやPrimのアルゴリズムを含めたいくつかのグラフアルゴリズムの実行時間を改善したことで最もよく知られている。
二項ヒープとよく似たデータ構造であるが、より償却実行時間が短くなる。フィボナッチヒープはグラフ内で最短経路を計算するためのダイクストラ法や、グラフの最小全域木を計算するプリム法の漸近的な処理時間を改善するのに用いられる。
特に、挿入、最小値検索、キー値減算、マージの操作は償却O(1)時間内で完了する。削除と最小値削除の操作は償却O(log n)時間内で完了する。つまり、空のデータ構造から始めた場合、最初のグループの「a」個の操作、および二番目のグループの「b」個の操作からなる任意のシーケンスは、O(a + b log a)の時間で完了する。
二項ヒープでは、このような一連の操作ではO((a + b)log(n))時間かかる。よってaよりbが漸近的に小さい場合はフィボナッチヒープは二項ヒープよりよい。
空の構造から一連の操作にかかる時間は上で述べた範囲内に収まるが、(非常にまれだが)いくつかの操作では非常に長い時間かかることがある(特にキー値減算、要素の削除、最小値の削除にかかる時間は、最悪の場合要素数に比例する)。この理由により、フィボナッチヒープ及びそれを用いているデータ構造はリアルタイムシステムにはふさわしくないかもしれない。