13

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

3
  • @Someprogrammerdude I just can't understand the connection between the interface of priority queue and the minimal operation (of underlying container) requirements. I mean, why the least needed are push_back, pop_back and front. (push_back is easy to understand of course)
    – Rick
    Jun 25, 2018 at 6:13
  • pop is used to remove the top element. So I think the underlying operation should also target the same element, right? let's say a vector, pop_back() and front(), does not target the same element.
    – Rick
    Jun 25, 2018 at 6:34
  • I think this is because the priority queue implementation happens through a heap. See stackoverflow.com/questions/2974470/…
    – unholy_me
    Jun 25, 2018 at 6:45

1 Answer 1

9

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.

4
  • Sorry I know little about heap (ಥ_ಥ). So as far as I can understand, you are saying that: E.g. I have 1,2,3 stored in a p-queue(using vector). After some sorting, it internally looks like [3][2][1]. When I call pop, it turns to be [1][2][3](swapping the top value to back) and then pop out [3], is that right?
    – Rick
    Jun 25, 2018 at 7:02
  • 1
    As commonly impl., the order after insertion of 1, 2, 3 would be 3, 1, 2. That is because after insertion of 2, the invariant is restored by moving 2 up (I call that "trickle up" in analogy to the "trickle down" described below): 2, 1. Then, you insert 3 and let that trickle up, so 2, 12, 1, 33, 1, 2 (swapping 2 and 3). On removal, as @o11c said, you swap front() and back(), do pop_back() and then let the new front(), "trickle down", so 3, 1, 22, 1, 32, 1 (done, no need for 2 to trickle down as it's already > than its (only) child).
    – Arne Vogel
    Jun 25, 2018 at 8:18
  • 1
    @Rick By the way, you might want to look at the descriptions of push_heap and pop_heap. The pq's push() can be implemented as c.push_back() followed by push_heap(). The pq's pop() can be implemented as pop_heap() followed by pop_back(). There is also make_heap() which could be useful when creating a pq from an iterator range (or initializer_list, if there were such a constructor) – first create the container by copying from the range, then make_heap().
    – Arne Vogel
    Jun 25, 2018 at 8:31
  • @ArneVogel Your detailed explanation is very helpful. I've read something about heap. Combining the answer and your comments now I have a vague understanding about it. Thanks :D.
    – Rick
    Jun 25, 2018 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.