Time complexity of a Priority Queue in C++

Question

Creating a heap takes O(n) time while inserting into a heap (or priority queue) takes O(log(n)) time.

Taking n inputs and inserting them into the priority queue, what would be the time complexity of the operation? O(n) or O(n*log(n)).

Also, the same result would hold in case of emptying the entire heap too (i.e. n deletions), right?

Answer 1

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.