Efficiency of the Stl Priority_Queue

Efficiency of the STL priority_queue

The priority queue adaptor uses the standard library heap algorithms to build and access the queue - it's the complexity of those algorithms you should be looking up in the documentation.

The top() operation is obviously O(1) but presumably you want to pop() the heap after calling it which (according to Josuttis) is O(2*log(N)) and push() is O(log(N)) - same source.

And from the C++ Standard, 25.6.3.1, push_heap :

Complexity: At most log(last - first) comparisons.

and pop_heap:

Complexity: At most 2 * log(last - first) comparisons.

How to do an efficient priority update in STL priority_queue?

I think you are out of luck with standard priority queue because you can't get at the underlying deque/vector/list or whatever. You need to implement your own - it's not that hard.

Time complexity of a Priority Queue in C++

If you have an array of size n and you want to build a heap from all items at once, Floyd's algorithm can do it with O(n) complexity. See Building a heap. This corresponds to the std::priority_queue constructors that accept a container parameter.

If you have an empty priority queue to which you want to add n items, one at a time, then the complexity is O(n * log(n)).

So if you have all of the items that will go into your queue before you build it, then the first method will be more efficient. You use the second method--adding items individually--when you need to maintain a queue: adding and removing elements over some time period.

Removing n items from the priority queue also is O(n * log(n)).

Documentation for std::priority_queue includes runtime complexity of all operations.

time complexity of priority_queue in C++

Heap insertion and extraction have the worst case complexity relative to the height of the tree, thus O(log N), plus the complexity of the underlying data structure.

In case of a vector, push_back has an amortized complexity O(1), and pop_back O(1).

Therefore it can be said that the total time complexity of push and pop of a priority_queue backed by a vector is O(log N).

Advantages of Setting priority_queue Container

Setting the underlying container makes it possible to separate out two logically separate concerns:

  1. How do you store the actual elements that make up the priority queue (the container), and
  2. How do you organize those elements to efficiently implement a priority queue (the priority_queue adapter class).

As an example, the standard implementation of vector is not required to shrink itself down when its capacity is vastly greater than its actual size. This means that if you have a priority queue backed by a vector, you might end up wasting memory if you enqueue a lot of elements and then dequeue all of them, since the vector will keep its old capacity. If, on the other hand, you implement your own shrinking_vector class that does actually decrease its capacity when needed, you can get all the benefits of the priority_queue interface while having the storage be used more efficiently.

Another possible example - you might want to change the allocator being used so that the elements of the priority queue are allocated from a special pool of resources. You can do this by just setting the container type of the priority_queue to be a vector with a custom allocator.

One more thought - suppose that you are storing a priority_queue of very large objects whose copy time is very great. In that case, the fact that the vector dynamically resizes itself and copies its old elements (or at least, in a C++03 compiler) might be something you're not willing to pay for. You could thus switch to some other type, perhaps a deque, that makes an effort not to copy elements when resizing and could realize some big performance wins.

Hope this helps!

C++ priority_queue

There is std::make_heap(...), which accepts whole N-range at once to build heap.

And as said in standard it has O(N) complexity. For example you can see how CLang implements std::make_heap, source is here.

Later you can use std::push_heap and std::pop_heap for adding and taking-out 1 by 1 element if needed in O(log N) time.

Also as suggested by @Jarod42 you can use just std::priority_queue, because one of its constructors accepts range (iterators) with N elements, this constructor has O(N) complexity too.

make_heap vs priority_queue efficiency when needed once per frame

Asymptotically there is no difference:

  1. Inserting in ordered collection N times is O(N log N).

  2. Sorting unordered collection of N elements is O(N log N).

So best way to select fastest solution is to implement both and check on real data.

I think storing events in container such as std::vector and sorting them at the end would be faster, because fast adding along with frame preparation will not invalidate CPU caches, that may occur during "long" and non-trivial O(log N) insert into std::priority_queue or std::map.

Also storing events in simple container (std::vector) and processing them when needed (sorting etc) looks more logical to me.



Related Topics



Leave a reply



Submit