Efficiency of the STL priority_queue

Solution 1:

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.

Solution 2:

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)

Solution 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.

Solution 4:

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