dary_heap

クラス · D 分ヒープ

template <class Key, class Value, class Comp = std::less<>, int D = 4>
struct dary_heap;

概要

D 分ヒープ

順序基準の Key と付随データ Value を保持し、Comp で Key を比較する。 Comp = std::greater<> で Key 最小をルートにする最小ヒープになる（binary_heap / fibonacci_heap と同じ規約）。連続領域（std::vector）に {key, value} を並べる flat 実装。 decrease-key は持たない。

テンプレートパラメータ

名前	説明
`Key`	順序基準。`Comp` で比較される側。
`Value`	付随データ。順序には関与しない。
`Comp`	`Key` の比較子。
`D`	分岐数（既定 4）。二分ヒープより木が浅く（log_D N）、`pop` の sift-down で子をまとめて見るため比較回数が増えるトレードオフがある。

備考

当環境のベンチでは Dijkstra 用途で std::priority_queue と概ね互角だった（明確な速度優位は確認できなかった）。binary_heap と並ぶ汎用ヒープとして提供する。

構築・破棄

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

メンバ関数

名前	説明	計算量
`empty`	空か返す	$O(1)$
`size`	要素数を返す	$O(1)$
`top`	最上位のkeyとvalueを返す	$O(1)$
`push`	要素を追加する	$O(\log_D n)$
`emplace`	要素を追加する	$O(\log_D n)$
`pop`	最上位の要素を削除する	$O(D\log_D n)$

dary_heap

概要

テンプレートパラメータ

備考

構築・破棄

メンバ関数

関連項目