STL and heap / priority queue

[vfunc]

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

 

[red floyd]

Is the STL priority queue a proper implementation of a heap with siftup
algorithm etc ? Yes.

How do you implement an STL priority queue (link to an
example) ?

#include <queue>

std:riority_queue<int> q;


You use push() to add members,
top() to get the top element and pop() to remove the top element.

> Is there a resort method, why ?

Yes, but you don't need it. It's for people implementing their own
heaps for various reasons.

 

[vfunc]

Thanks red floyd, are you related to pink ? Are you back at the hotel ?

 

[Mark P]

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

Technically a priority queue is an abstract data type whereas a heap is
a specific data structure which *can* be used to implement a priority
queue. AFAIK, there's no requirement or guarantee that the priority
queue is implemented as a heap (though in practice you're likely to find
that it is).

There is no resort method in the priority_queue interface.

 

[red floyd]

There is no resort method in the priority_queue interface.

No, but there is std::make_heap(), if you want to roll your own priority
queue. Also, priority_queue is available for private inheritance (the
underlying container is a protected member).