471,593 Members | 1,848 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,593 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 8845
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 discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

4 posts views Thread by Andre Paim Lemos | last post: by
5 posts views Thread by Dan H. | last post: by
5 posts views Thread by Ook | last post: by
4 posts views Thread by vfunc | last post: by
4 posts views Thread by jjh5030 | last post: by
reply views Thread by XIAOLAOHU | last post: by
reply views Thread by leo001 | last post: by
reply views Thread by Anwar ali | last post: by

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.