Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does a priority queue require front(), pop_back() from the underlying container instead of back(), pop_back()?

Tags:

c++

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()"?

like image 417
Rick Avatar asked Jun 25 '18 06:06

Rick


1 Answers

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.

like image 99
o11c Avatar answered Oct 14 '22 08:10

o11c