MLB - その３。

今回は decrease-key と extract-min について。

■準備■
・点 v に対し、「c(v) = 最小枝長」とする。枝がない場合は「c(v) = infinity」。
・点 v に対し、d(v) はポテンシャル値。
・バケットを補助する集合 F を用意する。
・「μ = 最後に取り出したポテンシャル値」とする。
　（１レベルのように、mod bucket_size でなく、素のポテンシャル値）


■decrease-key
u が格納されている B(i,j) から点 u を削除し、
新たなポテンシャル d(u) を B(i,j) に挿入する


■extract-min
空でないレベルのうち、最も低いものを探す。レベル i とする。
レベル i のうち、空でない最初のバケットを探す。j とする。

if (i == 0) {
　B(i,j) から点 u を削除する。
}
else if (i > 0) {
　B(i,j) のすべての要素を確認し、最も小さな要素 u を B(i,j) を削除する。
}

μ = d(u) とし、点 u を次の探索点とする。

点μが増加すると、それまでに挿入していた点の整合性が保てなくなるために、バケットの位置を変える必要がある。


流れとしてはこのような形ではあるが、高速化するための工夫がいくつか存在するので、ソースコードも合わせて確認していこう。