Update STL Priority Queue when modifying references to internal data

Question

Lets say I am writing Dijkstra's Algorithm, and I have a priority queue that is keeping the shortest distance node on the top. However as I traverse the graph I will be updating the distance to that vertex. I have placed references to all vertices in the priority queue that are contained in the data structure. Now as I update the vertices in the data structure, I would like for the data in the priority queue to adapt to those changes, so the nearest node is always on top. However, after stepping through my application with the debugger, I have noticed that the priority queue does not update itself. How do I get it to do this, without re-inserting all vertices back into it?

Answer 1

STL priority_queue assumes that you only use the push() and pop() methods to modify the data structure. It does not track changes to the data structure.

After modifying the interior of the priority_queue's underlying container you need to call make_heap() on the container to restore the heap property. STL priority_queue does not provide iterators on the underlying container. Instead you need to manually manage a deque or a vector as a priority queue and call make_heap(), push_heap(), and pop_heap() as needed.