min heap (priority queue)

[imutate@hotmail.co.uk]

How do you use std::priority_q ueue 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_q ueue <intidx, int>; ? Where does the comparison
fit into it ?

[red floyd]

Re: min heap (priority queue)

imutate@hotmail .co.uk wrote:

How do you use std::priority_q ueue 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_q ueue <intidx, int>; ? Where does the comparison
fit into it ?
>

Use a priority queue of std::pair<int int>.

[Rolf Magnus]

Re: min heap (priority queue)

imutate@hotmail .co.uk wrote:

How do you use std::priority_q ueue 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.

[Greg]

Re: min heap (priority queue)


red floyd wrote:

imutate@hotmail .co.uk wrote:

How do you use std::priority_q ueue 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_q ueue <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.

[Greg]

Re: min heap (priority queue)


Rolf Magnus wrote:

imutate@hotmail .co.uk wrote:
>

How do you use std::priority_q ueue 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_q ueue<

...but then what ?

[red floyd]

Re: min heap (priority queue)

Greg wrote:

red floyd wrote:

>imutate@hotmail .co.uk wrote:

>>How do you use std::priority_q ueue 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_q ueue <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.

[Greg]

Re: min heap (priority queue)

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_q ueue<int,
std::vector<int , std::allocator< int,
std::less<int pq;

This looks more promising...

std::priority_q ueue<int,
std::deque<int, std::allocator< int,
std::less<int pq;