swap - その３。

ボトルネックである swap へいろいろ工夫はしているが、今回変わった挙動を示しているので、紹介する。

以前この blog 行ったものであるが、swap() は、insert() や decease_key()、extract_min() で呼び出されている。しかしながら、extract_min() での swap() が全体のうちのかなりを占めている。

そのため swap() の工夫を extract_min() で採用すると、もちろん性能は上昇する。
これは当たり前のように思えるのだが、insert() や decease_key() へ適応すると、低速化してしまう。