By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,159 Members | 882 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,159 IT Pros & Developers. It's quick & easy.

min heap (priority queue)

P: n/a
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
Share this Question
Share on Google+
6 Replies


P: n/a
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

P: n/a
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

P: n/a

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

P: n/a

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

P: n/a
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

P: n/a
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.