ダイクストラ法向けの優先キューの一つで、正式には redistributive heap というそうだ。
K = log2(maxlen) + 2 だけの bucket を確保する。これは固定。各 bucket には格納すべきデータの範囲を次のように初期化する。
B[0].range = [0]
B[1].range = [1]
B[2].range = [2^(2-1), 2^2-1]
B[3].range = [2^(3-1), 2^3-1]
...
B[K].range = [2^(K-1), infinity]
insert / decreasekey(delete & insert) はこの範囲をもとに行われる。この優先キューのウリである extractmin では、最も小さい空でない bucket に格納されるデータをそれまでの bucket に再配置(redistribution) を行う。それに伴い range も更新される。
最も小さい空でない bucket が B[t] であり、次探索点のポテンシャルが new_base となる場合を例に挙げ説明すると、各 bucket の範囲は
B[0].range = [new_base]
B[1].range = [new_base+1]
B[2].range = [new_base+2^(2-1), new_base+2^2-1]
B[3].range = [new_base+2^(3-1), new_base+2^3-1]
...
B[t].range = [new_base+2^(t-1), 2^t-1]
B[t+1].range = [2^(t+1-1), 2^(t+1)-1]
...
B[K].range = [2^(K-1), infinity]
となる。