STL priority_queue
Author
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?
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().
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().
Quote:Original post by beany_boz
It also says that items can be added and removed in constant complexity.
Where does it say that?
Author
It says it here:
http://msdn2.microsoft.com/en-us/library/4ef4dae9.aspx
In the fourth paragraph under Remarks
http://msdn2.microsoft.com/en-us/library/4ef4dae9.aspx
In the fourth paragraph under Remarks
Author
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.
Is there somewhere you can point me for information about fibonacci heaps.
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.
Author
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.
The msdn2 domain is for the beta documentation, which means that it's not necessarily reliable. The equivalent page on the main MSDN site does not list the operation times as constant.
Fibonacci heaps were invented for "decrease key" operation. Everything other has the same (amortized) complexity.
Pure BS. It must be a typo or something.
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.
Author
Fair enough, I didnt notice it was msdn2, I just googled priority_queue. I'll watch out for that in future.
Thanks
Thanks
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
