fibonacci_heap

クラス · フィボナッチヒープ（decrease-key 対応）

template <class Key, class Value, class Comp = std::less<>>
struct fibonacci_heap;

概要

フィボナッチヒープ（decrease-key 対応）

順序基準の Key と付随データ Value を保持し、Comp で Key を比較する。 Comp = std::greater<> で Key 最小をルートにする最小ヒープになる （binary_heap / dary_heap と同じ規約）。 ノードを std::vector のプールに置き int インデックスで連結する index-pool 実装で、new/delete を一切行わない（コピー・ムーブも自動で正しい）。 push は安定なハンドルを返し、update で decrease-key できる。

備考

• pop したノードはプールから物理削除しない（ハンドルの寿命は呼び出し側管理）。

構築・破棄

メンバ関数

メンバ型

メンバの詳細

update

void update(handle h, Key key);

ハンドルの順序基準 key を更新する（ルート側へ近づく更新のみ反映）。

最小ヒープ（greater<>）では「より小さい key」への更新、つまり decrease-key に対応する。逆向きの更新は無視する。

• 計算量: 償却 $O(1)$

handle

struct handle;

push が返す安定ハンドル。update に渡してその要素を decrease-key する。

既定構築（handle{}）は無効値で bool 文脈で false。

• 計算量: 構築・比較は $O(1)$