Radix Heap
Operations
非負整数の key が紐づけられた要素の集合を扱う.
集合の大きさを$ nとする.
$ \mathtt{new}で固定した正整数$ cに対して, 以下の条件を満たす必要がある.
$ \mathtt{insert}(x, v)の際, 直近に削除された key が存在する場合, それを$ yとすると$ v \in \lbrack y, y + c\rbrack
空間計算量$ \Theta(n + \log c)
$ \mathtt{new}(c)
$ cを設定して空のヒープを作成する.
時間計算量$ \Theta(\log c)
$ \mathtt{insert}(x, v)
$ vを key とする要素$ xを追加する.
時間計算量$ \Theta(\log c) \ \rm amortized
$ \mathtt{delete \ min}()
最小の key を持つ要素を削除し, 返す.
時間計算量$ \Theta(\log c) \ \rm amortized
$ \mathtt{decrease}(x, v)
$ xの key を$ vに減少させる.
時間計算量$ \Theta(1) \ \rm amortized
Summary
辺のコストが正整数のグラフに対する Dijkstra 法に向いたヒープ.
要素をその key に応じた複数のバケットに分類して保持する.
$ \{9, 11, 14\}に$ \mathtt{delete \ min}を行った際の再割り当ての様子
https://gyazo.com/2266132db3231b1857356aea953ca765
$ \mathtt{delete \ min}の際に再割り当てされた要素は真に小さい index のバケットに移動することから, $ \Omicron(\log c)の計算量が達成される.
References
Notes
Implementations
Problems