Skew Heap

個人的メモ

$2$ つの木の併合(meld) 操作が本質で ($a$ を根とするヒープ, $b$ を根とするヒープ) の併合は単に $a, b$ の値の大きい方を根として, 例えば $a$ の値の方が大きければ $a$ の左の子($a$->$l$)を ($a$->$l$ を根とするヒープ, $b$ を根とするヒープ) を併合した結果の根とすればよい. ただこのままではもちろんマズい. 例えば $10, 9, 8,\cdots, 1$ のように要素を降順に挿入する場合木が偏り, 挿入時に毎回要素数に比例する深さまでたどる必要がある. これを防ぐために併合が終わって帰るときに子の左右を反転するという操作を行う.
実際これを行うことで push(), pop(), meld() をならし $\O( \log n)$ で行うことができる. 計算量の議論についてはここにのっている. ちなみに最後に反転を行わず, その代わりにマージの際にどちらをどちらの子にするかをランダムに決めるみたいなことをしても一応期待計算量 $\O (\log n)$ になる.
Hu-Tucker のアルゴリズム(最適二分探索木を求めるアルゴリズム) にも用いられているそうです(参考 最適平衡二分探索木).

（備忘録)
meld の計算量が $\log$ になることを示す. これにより, push および pop にかかる計算量も $\log$ になることが分かる.
頂点 $u$ とその親 $p$ を考える. $u$ が左の子なら left, 右の子なら right と言うようにする. また ($u$ を根とする部分木のサイズ) > ($p$ を根とする部分木のサイズ) $/ 2$ なら $u$ を heavy, そうでないなら light と言うようにする.
ここでポテンシャルをヒープ内に含まれる left かつ heavy なノードとする(根は left heavy と考える). このとき頂点数 $n_1$ でポテンシャルが $h_1$ のヒープ $H_1$ と頂点数 $n_2$ でポテンシャルが $h_2$ のヒープ $H_2$ の meld を考える. この meld にかかる実際の計算量は $H_1$ の根から左の子をたどっていったときのパス(最左パスと呼ぶことにする)の長さ と $H_2$ の根から左の子をたどっていったときのパスの長さの和になる. ここでその値を left heavy なノードと left light なノードに分けて考えると, (実際にかかる計算量) $\le h_1 + h_2 + \log n_1 + \log n_2 + 2$ となる. 根からのパス上にある light ノードの個数は log(ヒープのサイズ) となることを用いた.
次にポテンシャルの変分を上から抑える. よって $H_1$ と $H_2$ の left heavy ノードに比べて meld 後の left heavy ノードがどれだけ増えうるかを考えると良い. $H_1$ と $H_2$ の最左パスは　meld 後に最右パスになるが, このとき新たにできる left heavy ノードはこの最右パス上のノードの左の子であり, それは最右パス上の right light なノードと対応している(兄弟関係にある)ことがわかる. 根からのパス上にある light ノードの個数は $\log$(ヒープのサイズ) であるという事実を再び用いると結局 (ポテンシャルの変分) $\le \log(n_1 + n_2) - h_1 - h_2$ と上から抑えることができる.
ゆえに (ならし計算量) = (実際にかかる計算量) + (ポテンシャルの変分) $\le \log(n_1 + n_2) + \log(n_1) + \log(n_2) + 2 \le 3 \log(n_1 + n_2)$ より meld 操作は $\log$ になる.