データ構造メモ（平衡二分木&ヒープ）

※自分用メモなので人に見せる体裁にはしてないです。あまり確認してないので間違ったこと書いてるかも
平衡二分木
備考
節点に部分木のサイズを持たせるなどすればrank_less_thanやkth_elementなどの追加の機能も可。
動的な列を扱うことも可能で要素の挿入削除、列の併合分割ができる動的なsegtreeとしても使える。
プログラミングコンテストでのデータ構造 2 http://www.slideshare.net/iwiwi/2-12188757
npca2013 木のはなし http://www.npca.jp/2013/
Algorithms with Python http://www.geocities.jp/m_hiroi/light/index.html#python_algo
AVL tree
赤黒木と比べれば圧倒的に実装しやすい、赤黒木より遅い印象はないけどよく知らない。
赤黒木
場合わけえぐいやつ。実装する気起きない。葉にだけ要素を持たせればmerge/splitもできる
treap
乱数で割り振る優先度に対してヒープになってるやつ期待値O(log n),merge/split可能、融合永続不可
randomized binary search tree(RBST)
どっちを根にするか乱択するやつ、merge/split可能、融合永続可
treapより好きだけど毎回乱数生成するからそれで遅くなったりするのかな？
splay tree
link-cut treeで使うやつ、ならしO(log n)、merge/split可能らしい
scapegoat tree
平衡でなくなったらその部分を壊して再構築。ならしO(log n)
kd treeは最悪O(n)だがこの方法でならしO(log n)にできるらしい
https://topcoder.g.hatena.ne.jp/spaghetti_source/20120901/1346460700
https://topcoder.g.hatena.ne.jp/spaghetti_source/20120908/1347059626
skip list
木ではないけど似たようなことができる。競技では使うことないだろうけど分散処理がしやすいらしい。
van Emde Boas tree
二分木じゃないけど各種操作がO(log log u),(uは普遍集合のサイズ)でできる謎木。
実測でも速いらしい
http://catupper.hatenablog.com/entry/20120830/1346338855

ヒープ
binary heap
pushとpopだけならこれが最強。固定長配列でよければさらに速くなる。
leftist heap
meld を最悪O(log n)で処理できる。永続化するならこれ
skew heap
ならしO(log n)になる代わりにメンバ変数が減ってコードがより短くなる。
http://hos.ac/blog/#blog0001
binomial heap
meld を最悪O(log n)で処理できるけど上2つと比べてそんなに速いわけでもなくて実装面倒。
pairing heap
meldable heapの中で最速らしいけど多分いらない
relaxed heap
insertを最悪O(1)で実行できる。使うことなさそうだし日本語の資料もないし実装する気ない。
http://emoken.net/blog2/item_2137.html
fibonacchi heap
観賞用
interval heap
minとmaxの取得、削除ができる。ビームサーチで使えそう？
https://topcoder.g.hatena.ne.jp/spaghetti_source/20121006/1349491389