あるコードのプロファイル結果で、プライオリティキューの操作が非常に大きな比率を占めていて、気になってたんだけど、その原因のバグがようやく分かった。
プライオリティキューの先頭以外の要素を削除したいときに、実際には削除せず後で取り出されたときに無視するということをしてた。
だけど、そうして「削除」したことにした要素を再度追加するときに、プライオリティキューの中にまだ残っている可能性を考慮せず、無条件に追加してしまっていたのだった。
結果として要素を重複して持つことになり、プライオリティキューが肥大化してしまっていたのだった。
よくこれでそれなりに動いてたな……