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

Question

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

Answer 1

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

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