MeldableHeap
クラス · 融合可能ヒープ（leftist heap / skew heap）
template <class T, class Comp = std::less<>, bool Leftist = true>
struct MeldableHeap;
概要
融合可能ヒープ（leftist heap / skew heap）
ノードをポインタで連結し、meld は右脊柱を辿って融合する。 ノード実体は std::deque のプールが所有する（要素アドレスが安定し、 new/delete を一切行わずリークもしない）。meld で別ヒープの要素を 取り込む際は相手のプールを shared_ptr で延命するだけなので、プールを コピーせず連結は $O(\log N)$ のまま。 Comp = std::less<> で最大ヒープ、std::greater<> で最小ヒープ。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
Leftist |
true なら leftist heap（rank 比較で子を交換、最悪 $O(\log N)$）、 false なら skew heap（無条件に子を交換、ならし $O(\log N)$）。 |
備考
meldは引数のヒープを空にして要素を取り込む破壊的操作。
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
空の融合可能ヒープを構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
empty |
空か返す | $O(1)$ |
size |
要素数を返す | $O(1)$ |
top |
最上位の値を返す | $O(1)$ |
push |
(1) 値を追加する (2) 値をムーブして追加する |
$O(\log n)$ |
emplace |
値を直接構築して追加する | $O(\log n)$ |
pop |
最上位の値を削除する | $O(\log n)$ |
meld |
rhsを空にして全要素を融合する | $O(\log(n+m))$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
value_type |
格納値の型 | 型別名であり実行時計算量はない |
メンバの詳細
push
// (1)
void push(const T &val);
// (2)
void push(T &&val);
(1) 値を追加する
- 計算量: $O(\log n)$
(2) 値をムーブして追加する
- 計算量: $O(\log n)$
meld
void meld(MeldableHeap &rhs);
rhsを空にして全要素を融合する
rhsのノードプールはshared_ptrで延命される。
- 計算量: $O(\log(n+m))$