c++ - 修改对内部数据的引用时更新 STL 优先队列

Question

假设我正在编写Dijkstra 算法，并且我有一个优先级队列，它将最短距离节点保持在顶部。但是，当我遍历图表时，我将更新到该顶点的距离。我已经在数据结构中包含的优先级队列中放置了对所有顶点的引用。现在，当我更新数据结构中的顶点时，我希望优先级队列中的数据能够适应这些变化，因此最近的节点始终位于顶部。但是，在使用调试器单步执行我的应用程序后，我注意到优先级队列不会自行更新。我如何让它做到这一点，而无需将所有顶点重新插入其中？

Answer 1

STL priority_queue 假设您只使用 push() 和 pop() 方法来修改数据结构。它不跟踪对数据结构的更改。

在修改priority_queue的底层容器的内部之后，您需要在容器上调用make_heap()来恢复堆属性。STL priority_queue 不在底层容器上提供迭代器。相反，您需要手动管理双端队列或向量作为优先级队列，并根据需要调用 make_heap()、push_heap() 和 pop_heap()。