468,484 Members | 1,973 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,484 developers. It's quick & easy.

STL and heap / priority queue

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

Sep 20 '06 #1
4 9974
vf***@talktalk.net wrote:
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::priority_queue<intq;
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.
Sep 20 '06 #2

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

Sep 20 '06 #3
vf***@talktalk.net wrote:
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.
Sep 20 '06 #4
Mark P wrote:
>
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).
Sep 21 '06 #5

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
6 posts views Thread by imutate | last post: by
4 posts views Thread by jjh5030 | last post: by
reply views Thread by NPC403 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.