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

STL and heap / priority queue

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


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

P: n/a

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

Sep 20 '06 #3

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

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