473,232 Members | 1,457 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,232 software developers and data experts.

min heap (priority queue)

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
fit into it ?

Sep 29 '06 #1
6 8983
im*****@hotmail.co.uk wrote:
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
fit into it ?
Use a priority queue of std::pair<int int>.
Sep 29 '06 #2
im*****@hotmail.co.uk wrote:
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) ?
Define a struct of everything you want to store and use that as element
type. Then define an appropriate operator< for that struct.

Sep 30 '06 #3

red floyd wrote:
im*****@hotmail.co.uk wrote:
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
fit into it ?
Use a priority queue of std::pair<int int>.
Why would you use a pair ? That is not right for a heap.

Oct 5 '06 #4

Rolf Magnus wrote:
im*****@hotmail.co.uk wrote:
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) ?

Define a struct of everything you want to store and use that as element
type. Then define an appropriate operator< for that struct.
OK
struct helt {
int intidx;
}

std::priority_queue<

...but then what ?

Oct 5 '06 #5
Greg wrote:
red floyd wrote:
>im*****@hotmail.co.uk wrote:
>>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
fit into it ?
Use a priority queue of std::pair<int int>.

Why would you use a pair ? That is not right for a heap.
Why not? He want a heap of two things: an index and an integer weight.
Define an operator< which sorts the pairs by weight, and you are fine
with a heap of pairs.
Oct 5 '06 #6
Use a priority queue of std::pair<int int>.

Why would you use a pair ? That is not right for a heap.

Why not? He want a heap of two things: an index and an integer weight.
Define an operator< which sorts the pairs by weight, and you are fine
with a heap of pairs.
I forgot my terminology I am talking about a queue that is implemented
as a heap. I don't need a deque (double ended queue, but knowing how
to implement one is good.)

Yes, i want to implement an equivalent to your definition, but I've
never heard of it being implemented like this. Elements in a heap or a
priority queue are weighted by definition.

Here is an example I find a bit confusing because using a vector does
not make sense (a vector is not a heap, although admitidely it could
store a queue)

std::priority_queue<int,
std::vector<int, std::allocator<int,
std::less<int pq;

This looks more promising...

std::priority_queue<int,
std::deque<int, std::allocator<int,
std::less<int pq;

Oct 5 '06 #7

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

Similar topics

4
by: Andre Paim Lemos | last post by:
Hi, I'm having some compiler problems when I try to use make_heap(), push_heap() and pop_heap(). I am compiling my code on gcc version 3.3.1 (SuSE Linux). I am using the heap related methods to...
5
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...
5
by: Ook | last post by:
I'm not sure this is technically a c++ question, maybe there is a better ng to ask, but I'll start here since I'm coding this in c++. What exactly is a max heap, and more specifically, how do you...
4
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
3
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 (...
4
by: jjh5030 | last post by:
This is a programming assignment. You are asked to work with pointers. Be aware that error messages are often not very helpful when your pointers point to bad locations. Therefore, reserve...
1
by: corey2024 | last post by:
i need to create a program that will implement a priorty queue for a global shipping company. the program needs to keep track of which package needs to leave the warehouse next. you can only interact...
6
by: viki | last post by:
I have vector 'vec' of integers which was made into valid heap using std::make_heap(). Then we change value of a single element vec, like: vec = new_value; Now this makes vec not a valid...
14
by: AlarV | last post by:
Hello everyone, here is my problem. I have to make a dynamic priority queue,which is a heap, and my book isn't helpful at all, so I have no clues on how to create it.. I read something like a static...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...

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.