Re: priority_queue cannot update element value
On Apr 10, 1:58 pm, thomas <FreshTho...@gmail.com> wrote:
I want to use a priority_queue like STL data structure.
But I found that priority_queue cannot update element value: only pop/
push is supported.
Obviously. Otherwise, it wouldn't be a priority queue (and
arbitrary updates would destroy the necessary ordering).
I'm using priority_queue to implement the prim MST algorithm.
So I need the priority_queue to contain the key[] values for
each vertex not included in the final tree. Of course the pop
and push operation is what I need, but I also need to update
the weight value.
Why? If you update the weight value, you invalidate the
ordering in the priority queue. You invalidate the solution set
you've built so far, and have to start over. So all you have to
do is destruct the existing priority queue, and create a new
one.
Can I use priority_queue to make it work? Or any other way to
use existing STL containers to implement the prim MST
algorithm?
A priority queue seems exactly what is needed to me.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34