radix_heap
クラス · 基数ヒープ（単調ヒープ）
template <std::unsigned_integral Key = unsigned, class Value = void>
struct radix_heap;
概要
基数ヒープ（単調ヒープ）
順序基準 Key（符号なし整数）で最小値を取り出す。取り出した値より小さい Key は以後 push できない（単調性）。Dijkstra など距離が単調増加する用途向け。 連続領域（std::vector）に値を並べる flat 実装で、new/delete を行わない。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
Key |
順序基準。符号なし整数で、最上位ビット位置によりバケットへ振り分ける。 |
Value |
付随データ。void なら順序基準のみを格納し、push(key) / top() -> Key の 1 引数 API になる。 |
備考
voidは内部でstd::monostateに正規化し、本体を 1 つに保つ。
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
空の基数ヒープを構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
size |
要素数を返す | $O(1)$ |
empty |
空か返す | $O(1)$ |
push |
(1) キーと付随値を追加する (2) キーを追加する |
償却 $O(\log C)$ |
emplace |
キーと付随値を直接構築して追加する | 償却 $O(\log C)$ |
top |
最小のキーと必要なら付随値を返す | 償却 $O(\log C)$ |
pop |
最小のキーを持つ要素を削除する | 償却 $O(\log C)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
key_type |
キーの型 | 型別名であり実行時計算量はない |
value_type |
付随値の型 | 型別名であり実行時計算量はない |
メンバの詳細
push
// (1)
void push(Key key, stored_value value) requires has_value;
// (2)
void push(Key key) requires(!has_value);
(1) キーと付随値を追加する
- 計算量: 償却 $O(\log C)$
(2) キーを追加する
- 計算量: 償却 $O(\log C)$