Pairing Heap
Operations
$ \mathtt{new}()
空のヒープを作成する
時間計算量$ \mathrm{O}(1)
$ \mathtt{find\_min}()
ヒープの最小の要素を返す
時間計算量$ \mathrm{O}(1)
$ \mathtt{delete\_min}()
ヒープの最小の要素を削除する
時間計算量$ \mathrm{O}(\log n)amortized
$ \mathtt{insert}(x)
ヒープに要素$ xを追加する
時間計算量$ \mathrm{O}(1)amortized
$ \mathtt{merge}(h)
ヒープ$ hの要素をすべて追加する
時間計算量$ \mathrm{O}(1)amortized
Summary
根となる要素と，子として空でないヒープのリストをもつ多分木．通常のヒープ順序を満たす (根は常に最小の要素をもつ)．
融合可能なヒープ (meldable heap) の一つ．
$ \mathtt{insert}(x)
根が$ x，子のリストが空であるようなヒープを作成し$ \mathtt{merge}する．
https://gyazo.com/55edebcc7b498ad4b3e0ddcc8abc85dc
$ \mathtt{merge}(h)
根が大きい方のヒープを，根が小さい方の子のリストに追加する．
https://gyazo.com/95e7b2c403a7024d013894c98e1634b3
$ \mathtt{delete\_min}()
根を削除する．子のリストを，まず前から順にペアを組みそれぞれ$ \mathtt{merge}する．それらを後ろから順に$ \mathtt{merge}して一つにする．
https://gyazo.com/a28e1a847b84e34ff6ddb31e4c250309
References
Chris Okasaki (2017) 純粋関数型データ構造 (稲葉一浩・遠藤侑介 訳) アスキードワンゴ