STL reheapifyの実装

Question

グラフアルゴリズムでは、最小の値を持つノードを見つける必要があります。

アルゴリズムのステップでは、このノードまたはその近傍の値を減らすことができ、その値に応じていくつかの重力を除去することができます。 また、毎回このノードのグラフ全体を検索したくはありません（それほど大きくない（< 1000ノード））。

私はSTLライブラリを見て、私が欲しいものをほとんど実行するヒープ構造を見つけました。ノードの挿入と削除は非常に高速ですが、ヒープ全体を使用せずにノードの値を変更しただけで、ヒープを高速に更新する方法はありますか？私はそれがプログラムの大きなボトルネックになると感じています。

Answer 1

最初の概念部分： ヒープ挿入メソッドを、コレクションの後ろから開始するのではなく、挿入の開始点として値を減らした要素で使用すると、すべてが機能します。

私はまだC++でこれを行っていませんが、std :: push_heapはそのように見えます。