最短路問題での計算量 - Binary Heap。

最短路問題に用いるバイナリヒープの関数は、挿入 insert()、キーの更新（単調減少） decrease_key()、最小ポテンシャル点を取り除く extract_min() の３つであるが、計算量はどれも log2(n) である。しかしながら、前回の記事に書いたように、extract_min() での swap() がそのほとんどを占めている。最短経路問題の特性を考慮すれば気づくことできるが、単純に log2(n) と書かれてしまうと誤った思い込みを持ってしまうこともあるように思える。最短路ソルバーの高速化を行っているうちに、計算量だけによって適切ではないような評価をされてしまっている手法がまだまだあるのではないかと考えるようになってきた。