フィボナッチヒープ
【英】:Fibonacci heap
ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O となりうるが, 回の挿入, 回の最小値の取り出し, 回の値の減少を行う合計の計算時間が O となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの に対しては計算時間が大きく, 実際には通常のヒープが多く使われている.
組合せ最適化: | パーフェクトグラフ予想 ヒープ ファセット制約 フィボナッチヒープ マッチング問題 メタヒューリスティクス ラグランジュ緩和法 |
フィボナッチヒープ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/02/21 22:30 UTC 版)
フィボナッチヒープ(英: Fibonacci heap)とは、計算機科学におけるデータ構造(ヒープ)の1つ。
- ^ 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.
- 1 フィボナッチヒープとは
- 2 フィボナッチヒープの概要
- 3 参照
- フィボナッチヒープのページへのリンク