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
seem to operate on the 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 are the requirements 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 does 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With