473,389 Members | 1,067 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,389 software developers and data experts.

priority_queue cannot update element value

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?
Apr 10 '08 #1
3 10187
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.
Apr 10 '08 #2
On Apr 10, 1:58 pm, thomas <FreshTho...@gmail.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:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jun 27 '08 #3
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.
Jun 27 '08 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
by: Aguilar, James | last post by:
Is there any way to use a priority_queue with pointers? The reason why I ask is that I want a data structure that contains pointers to objects, not copies of objects. Also, I want them to be...
9
by: Rich S. | last post by:
Hi In an earlier posting I was asking how to read thru millions of data records keeping the top 2000 (where the top values are based upon a field in the record) and niklasb suggested using a...
3
by: zl2k | last post by:
hi, all Here is what I want to do: to wrap my self defined class in a shared_ptr and then insert it into the priority_queue. The priority_queue should pump the least element of the self defined...
9
by: Henning Hasemann | last post by:
I'm using a stl-priority queue and want - find out if a certain item is contained in the queue - to be able iterate over all items without having to pop() them, order does not matter. I couldnt...
18
by: J.M. | last post by:
I would like to use a data structure (e.g. from the STL) that always allows me to retrieve the largest element. (I want to push in elements, and remove the largest, push in further elements, etc.)...
6
by: Eric Lilja | last post by:
Hello, I have a the following priority_queue: priority_queue<pair<int, string pq; AFAICT, priority_queues doesn't support iterators. My question: is there a way to print its contents without...
8
by: thomas | last post by:
priority_queue usually uses the greater<intpredicate function. But as you know, we don't always use priority_queue<int>. Actually we may need the "priority_queue<pair<int,int>,...
24
by: Joe, G.I. | last post by:
Can anyone help me w/ a priority_queue. I'm generating MyEvent classes and I put them on a priority_queue, but I don't know how to get them in priority. The priority is the event w/ the smallest...
5
card
by: card | last post by:
I was wondering if anyone has a definitive answer on whether the STL priority_queue is dynamic? What I mean by this is best illustrated by a simple example. Suppose I have a priority queue of class...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
0
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.