Hi guys,
Just wondering what you'd recommend in terms of a C++ priority queue
implementation that supports bubble-up and bubble-down operations
please? std::priority_q ueue doesn't seem to support doing that, and I
couldn't find an alternative in Boost. I could write my own, but that
feels a little bit like reinventing the wheel, so I thought it was worth
asking first.
Cheers,
Stu 3 5216
Stuart Golodetz wrote:
Hi guys,
Just wondering what you'd recommend in terms of a C++ priority queue
implementation that supports bubble-up and bubble-down operations
please? std::priority_q ueue doesn't seem to support doing that, and I
couldn't find an alternative in Boost. I could write my own, but that
feels a little bit like reinventing the wheel, so I thought it was worth
asking first.
Cheers,
Stu
When I said "bubble-up" and "bubble-down", what I really meant was
increase key and decrease key (not necessarily respectively). Just to
clarify :-)
Stu
On Aug 5, 2:25*pm, Stuart Golodetz
<sgolod...@NdOi SaPlA.pMiPpLeEx A.ScEomwrote:
Stuart Golodetz wrote:
Just wondering what you'd recommend in terms of a C++ priority queue
implementation that supports bubble-up and bubble-down operations
please? std::priority_q ueue doesn't seem to support doing that, and I
couldn't find an alternative in Boost. I could write my own, but that
feels a little bit like reinventing the wheel, so I thought it was worth
asking first.
When I said "bubble-up" and "bubble-down", what I really meant was
increase key and decrease key (not necessarily respectively). Just to
clarify :-)
Technically a PQ doesn't support bubble/key operations. You're wanting
a heap. Check out std::make_heap, std::sort_heap, and related
functions.
Cheers! --M
mlimber wrote:
On Aug 5, 2:25 pm, Stuart Golodetz
<sgolod...@NdOi SaPlA.pMiPpLeEx A.ScEomwrote:
>Stuart Golodetz wrote:
>>Just wondering what you'd recommend in terms of a C++ priority queue implementatio n that supports bubble-up and bubble-down operations please? std::priority_q ueue doesn't seem to support doing that, and I couldn't find an alternative in Boost. I could write my own, but that feels a little bit like reinventing the wheel, so I thought it was worth asking first.
When I said "bubble-up" and "bubble-down", what I really meant was increase key and decrease key (not necessarily respectively). Just to clarify :-)
Technically a PQ doesn't support bubble/key operations. You're wanting
a heap. Check out std::make_heap, std::sort_heap, and related
functions.
Cheers! --M
Thanks, think I may have been confusing the interface and the
implementation (since PQs are often implemented as heaps internally).
That being said, it is looking increasingly as if I'll have to cook my
own at least to some extent: I need dictionary lookup for the decrease
key/increase key operations, I don't think I can just use the simple
approach which is possible when you already have a pointer to the
element whose key you're trying to change. But I'll take a look at the
heap operations and see if I can make use of them somehow to avoid
completely reinventing things...
Cheers for the help :-)
Stu This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Aaron W. LaFramboise |
last post by:
Hello,
I understand that an easy way to make the standard std::priority_queue
stable is by including an integer stamp with each node that is
incremented each time a new node is pushed into the queue. However, no
matter what reasonably-sized type I use for the stamp, eventually the
stamp will 'wrap around' and possibly cause incorrect...
|
by: Dan H. |
last post by:
Hello,
I have implemented a C# priority queue using an ArrayList. The objects
being inserted into the priority queue are being sorted by 2 fields, Time
(ulong) and Priority (0-100).
When I enqueue, I do a binary search on where to put the object and then
insert using that index and arraylist.insert(index, obj)
The bottom of my...
|
by: Crirus |
last post by:
hello
I read somewhere about priority queue...what is that and Vb net have such
class?
--
Ceers,
Crirus
------------------------------
If work were a good thing, the boss would take it all from you
|
by: vfunc |
last post by:
Is the STL priority queue a proper implementation of a heap with siftup
algorithm etc ? How do you implement an STL priority queue (link to an
example) ? Is there a resort method, why ?
Thanks
|
by: imutate |
last post by:
How do you use std::priority_queue to store say an index type (call it
intidx) and sort using another integer type (but smallest weight at the
top) ? How do you pop off the top index ? I mean top() returns the
top element but how do you access the index and the weight.
Is it std::priority_queue <intidx, int>; ? Where does the comparison...
| |
by: vidishasharma |
last post by:
Can somebody suggest good URL which contains code for merging of 2 or
more priority queues in c#.
|
by: Chris Lasher |
last post by:
Hello,
I am working with large graphs (~150,000 to 500,000 nodes) which I
need decompose node-by-node, in order of a node's value. A node's
value is determined by the sum of its edge weights. When a node is
removed from the graph, its neighbors' values must be updated to take
into account the removed edges.
I was told to look for a...
|
by: PicO |
last post by:
i need some explanation about the difference between priority queue &
set & heap ... as they all sort the data in ( n log n ) ... but the
only i see that priority queue only can pop the top ( maximum
element ) while set and heap can erase any element ...
|
by: kieselchen |
last post by:
hej,
i would like to use the stl priority queue, but i occasionally have to remove random elements form the queue. is there any possibility for that?
concert problem:
i'd like to use priority queue for pending actions which i have to perform at a certain time. this actions may also be timeouts. this timeouts i would like to remove as soon as...
|
by: morris11 |
last post by:
I want to implement a priority queue based on a sorted linked list. The remove operation on the priority queue should remove the item with a smallest key. Can anybody give me an idea how to do that?
|
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, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
| |
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 tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
|
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 Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...
| |