From C++ Primer and also https://en.cppreference.com/w/cpp/container/priority_queue, I know:
A priority_queue requires random access in addition to the front, push_back, and pop_back operations;
I also read this blog post from Google and know:
- push: add a new element to the queue,
- pop: remove the largest element of the queue,
- top: access the largest element of the queue.
push should be implemented by
push_back, no problem. And
top seems to operate on same element. One is to access it, the other removes it. So I think these two operations should be implemented by
So I am confused, why the requirements are
Let's for example assume the underlying container is a
vector and with some int elements let's say
1,2,3,4,5,6. How do the adaptor interface "
top()" work with the underlying "
pop() on a
priority_queue is ultimately removing the top element, it must maintain the invariant, which would not happen if all the elements simply shifted over. Thus, it works by swapping the top value from
pop_back()ing that, then swapping the displaced value with one of its children until the invariant is restored.
push_back() and then performs a series of swaps, albeit in the other direction.
Note: since C++ uses a max-heap (contrary to common convention), the invariant is that any element must be larger than both of its children (if they exist). Since most useful problems involve a min-heap, you almost always have to specify
std::greater<> as the
Compare template argument.