priority_queue cannot update element value

[thomas]

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.

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.

Can I use priority_queue to make it work?
Or any other way to use existing STL containers to implement the prim
MST algorithm?

[Fei Liu]

Re: priority_queue cannot update element value

thomas 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.
>
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.
>
Can I use priority_queue to make it work?
Or any other way to use existing STL containers to implement the prim
MST algorithm?

Sounds like you should use a set or map and implement the push/pop
behavior by youself. This will incur some performance penalty because
the set/map push-pop will all perform worst case O(lgN).

Another thing you could do is have 2 separate data structures one is the
priority queue of pointer type and the other can be a simple vector of
the real objects. then you can update weight of the element in the vector.

[James Kanze]

Re: priority_queue cannot update element value

On Apr 10, 1:58 pm, thomas <FreshTho...@gm ail.comwrote:

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.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Jerry Coffin]

Re: priority_queue cannot update element value

In article <06e4abfb-dba7-4e6f-8607-
82e35b5f1c6a@h1 g2000prh.google groups.com>, FreshThomas@gma il.com says...

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.
>
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.
>
Can I use priority_queue to make it work?
Or any other way to use existing STL containers to implement the prim
MST algorithm?

Since you need to do more than just add and remove items, you can't use
a true priority queue. You should be able to use std::make_heap in a
suitable container. IIRC, for Prim's algorithm what you really want is a
Fibonacci heap. Doing a quick glance through the standard, there's
nothing to indicate that it provides a Fibonacci head instead of the
usual binary heap. Prim's algorithm works with binary heaps, but gives
only O(E lg V) instead of the desired O(E + V lg V) -- you normally only
use Prim's algorithm when E is considerably smaller than V, in which
case this is a substantial win.

There's been Fibonacci heap code in the "Pending" area on Boost for
quite a while. Even though that means it's not an official part of the
library, you might find it quite useful. For that matter, a quick check
indicates that the Boost Graph library already includes an
implementation of Prim's algorithm. It looks like the stock
implementation uses a binary heap though...

--
Later,
Jerry.

The universe is a figment of its own imagination.