Skew Heap
(data-structure/skew-heap.hpp)
Skew Heap
Skew Heapを実装したライブラリ。
概要
Skew Heapとは、ヒープ同士のマージ(融合, meld)やヒープ全体に定数を加算する操作を高速に行うことが出来るヒープである。アルゴリズム自体は一読して理解できる程度に簡潔だが計算量解析は難しい。(参考)
ヒープ全体への定数の加算を諦める代わりに特定のノードの値を高速に更新する機能をつけることが出来て、ダイクストラ法の定数倍高速化に利用される。
使い方
平衡二分木などのライブラリと同様に根のノードをポインタで持つ形で管理する。push, pop
などの操作を行ったときに根が変化するので、返り値で新しい根を返す。
根に最小の値が入っていて、p->key + p->add
でkey
を、p->idx
でkey
に関連する情報を取得することが出来る。
-
SkewHeap<T, isMin = true>
: 型T
をkey
の型として最小値が根になるヒープ。isMin
をFalseにすると最大値が根になる。
-
Ptr push(Ptr x, const T& key, int idx)
: 根をx
とするヒープに(key, idx)
を挿入して新しい根へのポインタを返す。
-
Ptr pop(Ptr x)
: 根のノードを削除して新しい根へのポインタを返す。
-
Ptr alloc(const T& key, int idx)
: (key, idx)
を持ったノードを新しく作成して、ポインタを返す。
-
meld(Ptr x, Ptr y)
: x
とy
を融合して新たな根のポインタを返す。
Required by
Verified with
Code
Back to top page