- A+

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 `pop`

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 `pop_front()`

and `front()`

or `pop_back()`

and `back()`

.

So I am confused, why the requirements are `front()`

and `pop_back()`

?

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 "`pop()`

, `top()`

" work with the underlying "`front()`

, `pop_back()`

"?

Although `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 `front()`

to `back()`

and `pop_back()`

ing that, then swapping the displaced value with one of its children until the invariant is restored.

Likewise, `push()`

calls `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.