🔒 Locked

STL priority_queue

Started by beany_boz Aug 20, 2006 at 7:58 AM 8 replies 1.1k views

Original Post

Aug 20, 2006 at 7:58 AM

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?

ToohrVyk

238

ToohrVyk

Aug 20, 2006 at 8:04 AM

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().

SiCrane

Mod

473

SiCrane

Aug 20, 2006 at 8:23 AM

Quote:
Original post by beany_boz
It also says that items can be added and removed in constant complexity.

Where does it say that?

beany_boz

Author

beany_boz

Aug 20, 2006 at 8:42 AM

It says it here:

http://msdn2.microsoft.com/en-us/library/4ef4dae9.aspx

In the fourth paragraph under Remarks

beany_boz

Author

beany_boz

Aug 20, 2006 at 8:45 AM

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.

ToohrVyk

238

ToohrVyk

Aug 20, 2006 at 8:51 AM

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.

beany_boz

Author

beany_boz

Aug 20, 2006 at 8:55 AM

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.

SiCrane

Mod

473

SiCrane

Aug 20, 2006 at 9:01 AM

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.