Skew Heap
#Heaps
Operations
全順序集合の$ n要素の部分多重集合を扱う.
空間計算量$ \Theta(n)
$ \mathtt{new}()
空のヒープを作成する.
時間計算量$ \Theta(1)
$ \mathtt{peek}()
ヒープの最小の要素を返す.
時間計算量$ \Theta(1)
$ \mathtt{pop}()
ヒープの最小の要素を削除して返す.
時間計算量$ \Omicron(\log n) \ \rm amortized
$ \mathtt{insert}(x)
ヒープに要素$ xを追加する.
時間計算量$ \Omicron(\log n) \ \rm amortized
$ \mathtt{meld}(h)
ヒープ$ hの要素をすべて追加する.
時間計算量$ \Omicron(\log n) \ \rm amortized
Summary
融合可能なヒープ (meldable heap) の一つ
heap property を満たす自由な形の二分木によって表現される.
$ \mathtt{meld}が基本的な操作で,$ \mathtt{insert}や$ \mathtt{pop}は$ \mathtt{meld}を用いて実装できる
$ \mathtt{insert}(x): 単一のノード$ xからなるヒープを作成し, $ \mathtt{meld}
$ \mathtt{pop}(x): 根の要素を取り出して左右の子同士を$ \mathtt{meld}
$ \mathtt{meld}は右の子をたどるパスをマージし, 最後にパス上のノードについて子を swap する.
References
D.D.Sleator and R.E.Tarjan, Self-adjusting heaps, SIAM J. Comput. 15(1), 52–69 (1986)
Leftist Heap & Skew Heap - hos.ac
Notes
近いデータ構造に, 最悪計算量を保証する Leftist Heap が存在する.
Implementations
Rust: noshi91/skew_heap