The documentation for std::priority_queue states the complexity of the push operation as:
Logarithmic number of comparisons plus the complexity of
Container::push_back.
And by default uses std::vector as the underlying container. However, push_back can only push elements to the end of the vector, while in a priority queue one might need to add elements somewhere in the middle of the vector, in which case all elements that follow have to be shifted to the right. In the worst case, when adding an element at the beginning, the push operation would incur the full O(n) cost. So how does the priority queue do it in logarithmic time? Why does it use a vector by default as opposed to some "easy insert and find" container such as a heap?
while in a priority queue one might need to add elements somewhere in the middle of the vector, in which case all elements that follow have to be shifted to the right
No. The right shift does not occur.
The new element is added to the end, at index i: O(1)
Then its priority is compared to its parent at index i/2 and swapped if of higher priority.
If a swap occurs, compare the next parent.
Repeat above 2 steps until at at index 0. O(log(i))