Efficiency of the STL priority_queue

Question

I have an application (C++) that I think would be well served by an STL priority_queue. The documentation says:

Priority_queue is a container adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is vector, but a different type may be selected explicitly.

and

Priority queues are a standard concept, and can be implemented in many different ways; this implementation uses heaps.

I had previously assumed that top() is O(1), and that push() would be a O(logn) (the two reasons I chose the priority_queue in the first place) - but the documentation neither confirms nor denies this assumption.

Digging deeper, the docs for the Sequence concept say:

The complexities of single-element insert and erase are sequence dependent.

The priority_queue uses a vector (by default) as a heap, which:

... supports random access to elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle.

I'm inferring that, using the default priority_queue, top() is O(1) and push() is O(n).

Question 1: Is this correct? (top() access is O(1) and push() is O(n)?)

Question 2: Would I be able to achieve O(logn) efficiency on push() if I used a set (or multiset) instead of a vector for the implementation of the priority_queue? What would the consequences be of doing this? What other operations would suffer as a consequence?

N.B.: I'm worried about time efficiency here, not space.

Answer 1

The priority queue adaptor uses the standard library heap algorithms to buld 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.

Answer 2

If the underlying data structure is a heap, top() will be constant time, and push (EDIT: and pop) will be logarithmic (like you are saying). The vector is just used to store these things like this:

HEAP:
             1
        2         3
      8 12   11 9

VECTOR (used to store)

1 2 3 8 12 11 9

You can think of it as the element at position i's children is (2i) and (2i+1)

They use the vector because it stores the data sequentially (which is much more efficient and cache-friendly than discrete)

Regardless of how it is stored, a heap should always be implemented (especially by the gods who made the STD lib) so that pop is constant and push is logarithmic

Answer 3

No. This is not correct. top() is O(1) and push() is O(log n). Read note 2 in the documentation to see that this adapter does not allow iterating through the vector. Neil is correct about pop(), but still this allows working with the heap doing insertions and removals in O(log n) time.

Answer 4

top() - O(1) -- as it just returns the element @ front.

push() -

• insert into vector - 0(1) amortized

• push_into_heap - At most, log(n) comparisons. O(logn)

  so push() complexity is -- log(n)

Answer 5

Q1: I didn't look in the standard, but AFAIK, using vector (or deque btw), the complexity would be O(1) for top(), O(log n) for push() and pop(). I once compared std::priority_queue with my own heap with O(1) push() and top() and O(log n) pop() and it certainly wasn't as slow as O(n).

Q2: set is not usable as underlying container for priority_queue (not a Sequence), but it would be possible to use set to implement a priority queue with O(log n) push() and pop(). However, this wouldn't probably outperform the std::priority_queue over std::vector implementation.