フィボナッチヒープ

出典: ORWiki

【ふぃぼなっちひーぷ (Fibonacci heap)】

$F\,$ ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O $(n)\,$ となりうるが, $n\,$ 回の挿入, $m\,$ 回の最小値の取り出し, $k\,$ 回の値の減少を行う合計の計算時間が O $(n+m+k\log n)\,$ となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの $n\,$ に対しては計算時間が大きく, 実際には通常のヒープが多く使われている.