Sign in to follow this  

STL priority_queue

This topic is 4136 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was just reading about STL priority_queues on the MSDN site. Apparently the default container class for a priority_queue is a vector. It also says that items can be added and removed in constant complexity. I assume that by remove it refers to the pop member function which is guaranteed to return the highest valued item according to the < operator. My problem with this is that surely adding an item to the priority_queue requires the container to look through the whole queue to find out where it should belong in the rankings, so how can it be constant complexity? Similarly if it just added it on the end and tried to find the highest item when it came to pop time, surely this too would require more than constant complexity. Does anyone understand this?

Share this post


Link to post
Share on other sites
If I remember correctly, priority_queue uses push_heap and pop_heap internaly, and these two guarantee logarithmic complexity, but not constant.

On the other hand, many other types of heaps exist, some of which allow removal in constant time, and others which allow insertion in constant time. I'm not certain if one exists that allows both in constant time.

EDIT: for instance, fibonacci heaps allow constant-time push() and top(), but logarithmic pop().

Share this post


Link to post
Share on other sites
Quote:
Original post by beany_boz
It also says that items can be added and removed in constant complexity.


Where does it say that?

Share this post


Link to post
Share on other sites
If a fibonacci heap allows constant time push and top then that would be enough for priority_queue because it only allows popping the highest valued member.

Is there somewhere you can point me for information about fibonacci heaps.

Share this post


Link to post
Share on other sites
Quote:
Original post by beany_boz
If a fibonacci heap allows constant time push and top then that would be enough for priority_queue because it only allows popping the highest valued member.


Removing an element (even the top one) from a fibonnaci heap destroys the heap structure. You have to spend some time rebuilding the heap back, which accounts for the increased complexity. By contrast, accessing the top element without removing it keeps the heap structure alive, so it doesn't require additional work.

Quote:
Is there somewhere you can point me for information about fibonacci heaps.


Wikipedia.

Share this post


Link to post
Share on other sites
I've just read up on Wikipedia about fibonacci heaps, and although insert and find minimum work in O(n), actually deleting the minimum, which is obviously what pop involves, is O(log n). So thats not good enough. I dont believe microsoft.

Share this post


Link to post
Share on other sites
Fibonacci heaps were invented for "decrease key" operation. Everything other has the same (amortized) complexity.

Quote:
MDSN
Adding elements to, removing elements from, and accessing elements in a priority_queue all have constant complexity.


Pure BS. It must be a typo or something.

Share this post


Link to post
Share on other sites

This topic is 4136 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this