I am using a d_ary_heap_indirect as a priority queue using a property map to store the priorities. However, I when I change the values in the priority property map and push vertices that are already in the queue into the queue again, it results in kind of an invalid state where the vertex appears in the queue twice at different positions. Here is a demo: http://programmingexamples.net/wiki/CPP/Boost/BGL/IndirectPriorityQueue It simply sets random priority values for every vertex, and pushes them all into the queue. It then does exactly the same thing again. You can see that some vertices appear twice in the queue at different positions. For example, vertex (3,0) occurs at position 0 in the queue, and again at position 6. Of course the priority values that are output are the same because the demo simply outputs the values that are currently in the priority property map, but I guess I would expect the two instances of a vertex to appear at back-to-back positions in the queue (as it should have used their current value to sort the queue)? Is there a way to replace a vertex in the queue when it is pushed instead of adding a second one? (like an std::set instead of the current behavior which is like std::multiset)? Thanks, David