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

Question

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

Answer 1

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

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