Hi I'm using a priority queue to organize a large number of Vertex's by a their '.getDist()' value. Smallest dist on top. I change the dist value externally (only to a smaller value, never bigger) sometimes, and I would like the pqueue to re-adjust itself. I thought simply pop()ing the top of the pqueue would do the trick, since it would cause it to percolate up/down, but I'm seeing cases where it fails to organize the Vertex's correctly. I also thought about rebuilding the pqueue each time form the old one, but can't find a way to do it. BTW, the complexity time must be very good. Any suggestions? Thanks for any input

std::priority_queue isn't designed for objects that change their heap value. If you really want to do this, manually manage your heap with the functions std::make_heap(), std::pop_heap() and std::push_heap(). When you change your heap values rerun std::make_heap().

Thanks SiCrane, looks like this will work fine for me. Do you mind giving me an example of how to use make_heap with a compare function? The value to compare is vertexName->getDist(). (The heap will keep pointers to Vertex's). Thanks

The standard c++ heap API works on containers whose items support strict-weak ordering. The simplest implementation would be: