内部データへの参照を変更するときにSTL優先度キューを更新する

Question

私はDijkstra's Algorithmと書いていますが、最短距離のノードを最上位に保っている優先キューを持っています。しかし、グラフをたどると、その頂点までの距離が更新されます。私は、データ構造体に含まれる優先度キューのすべての頂点への参照を配置しました。データ構造内の頂点を更新するときに、優先キューのデータがこれらの変更に適応するようにしたいので、最も近いノードは常に上にあります。しかし、私のアプリケーションをデバッガでステップ実行した後、優先度キューが更新されないことに気付きました。すべての頂点をその中に再挿入することなく、これをどうやって行うのですか？

Answer 1

STL priority_queueは、push（）およびpop（）メソッドのみを使用してデータ構造を変更することを前提としています。データ構造の変更は追跡されません。

priority_queueの基になるコンテナの内部を変更した後、ヒーププロパティを復元するには、コンテナでmake_heap（）を呼び出す必要があります。 STL priority_queueは、基になるコンテナにイテレータを提供しません。代わりに、dequeまたはベクトルを優先度キューとして手動で管理し、必要に応じてmake_heap（）、push_heap（）およびpop_heap（）を呼び出す必要があります。