Why priority queue require front(), popback() of underlying container instead of back(), popback()?

  • A+
Category:Languages

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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: