In article <06e4abfb-dba7-4e6f-8607-

82**********@h1g2000prh.googlegroups.com>,

Fr*********@gmail.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.