binary_heap

クラス · 二分ヒープ（decrease-key 対応）

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

概要

二分ヒープ（decrease-key 対応）

順序基準の Key と付随データ Value を保持し、Comp で Key を比較する。 Comp = std::greater<> で Key 最小をルートにする最小ヒープになる（dary_heap / fibonacci_heap と同じ規約）。連続領域（std::vector）に要素を並べる flat 実装で、new/delete を一切行わない。push は安定なハンドルを返し、pop/push/update を挟んでもそのハンドルで同じ要素を指し続けられる（要素はノード ID で管理し、ヒープ配列の再配置から切り離す）。

テンプレートパラメータ

名前	説明
`Key`	順序基準。`Comp` で比較される側。
`Value`	付随データ。順序には関与しない。
`Comp`	`Key` の比較子。`comp(a, b) == true` のとき a が b より下位（ルートから遠い側）になる。

構築・破棄

名前	説明	計算量
`(constructor)`	空のヒープを構築する	$O(1)$

メンバ関数

名前	説明	計算量
`empty`	空か返す	$O(1)$
`size`	要素数を返す	$O(1)$
`top`	最上位のkeyとvalueを返す	$O(1)$
`push`	要素を追加して安定ハンドルを返す	$O(\log n)$
`emplace`	要素を追加して安定ハンドルを返す	$O(\log n)$
`pop`	最上位の要素を削除する	$O(\log n)$
`update`	ハンドルの順序基準 `key` を更新する（ルート側へ近づく更新のみ反映）。	$O(\log n)$

メンバ型

名前	説明	計算量
`handle`	`push` が返す安定ハンドル。`update` に渡してその要素を decrease-key する。	構築・比較は $O(1)$

メンバの詳細

update

void update(handle h, Key key);

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

comp(現在の key, key) == true（= 現在値が下位）のときだけ上書きし sift-up する。最小ヒープ（greater<>）では「より小さい key」への更新、つまり decrease-key に対応する。逆向きの更新は無視する。

計算量: $O(\log n)$

handle

struct handle;

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

既定構築（handle{}）は無効値で、bool 文脈で false。要素を pop してもハンドルは無効化しない（呼び出し側で寿命を管理する）。

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

メンバ	説明
`handle`	無効なハンドルを作る
`operator bool`	有効なハンドルなら true を返す
`operator==`	2 つのハンドルが同じ要素を指すか比較する