min heap (priority queue)

[imutate]

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

 

[red floyd]

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

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

 

[Rolf Magnus]

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

 

[Greg]

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

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

 

[Greg]

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:riority_queue<

...but then what ?

 

[red floyd]

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]

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

This looks more promising...

std:riority_queue<int,
std::deque<int, std::allocator<int> >,
std::less<int> > pq;