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:
- How do you store the actual elements that make up the priority queue (the container), and
- 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:
Inserting in ordered collection N times is O(N log N).
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
Defining Global Constant in C++
Polymorphic_Allocator: When and Why Should I Use It
Lambda Capture as Const Reference
Osx - Replace Gcc Version 4.2.1 with 4.9 Installed via Homebrew
Why Does the Standard Differentiate Between Direct-List-Initialization and Copy-List-Initialization
Could You Recommend Some Guides About Epoll on Linux
Scale and Rotation Template Matching
How to Find All the Functions Exposed by a Dll
Fatal Error Lnk1104: Cannot Open File 'Libboost_System-Vc110-Mt-Gd-1_51.Lib'
Converting Data from Glreadpixels() to Opencv::Mat
What Is the Meaning of Clang's -Wweak-Vtables
Linux Perf: How to Interpret and Find Hotspots
How to Pretty-Print Stl Containers in Gdb
Clock Function in C++ with Threads