c++ - 为什么优先级队列需要底层容器的front()、pop_back()而不是back()、pop_back()？

Question

来自 C++ Primer 以及 https://en.cppreference.com/w/cpp/container/priority_queue ，我知道:

A priority_queue requires random access in addition to the front, push_back, and pop_back operations;

我也读过 blog post来自 Google 并知道:

• 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应该由push_back实现，没问题。pop 和 top 似乎在同一个元素上进行操作。一个是访问它，另一个是删除它。所以我觉得这两个操作应该由pop_front()和front()或者pop_back()和back()<实现。

所以我很困惑，为什么要求front()和pop_back()？

例如，假设底层容器是 vector 并带有一些 int 元素，例如 1,2,3,4,5,6。适配器接口(interface)“pop(),top()”如何与底层的“front(),pop_back() ”？

Answer 1

虽然pop()在 priority_queue最终删除顶部元素，它必须保持不变量，如果所有元素都简单地移动就不会发生这种情况。因此，它通过交换 front() 中的最高值来工作。至back()和 pop_back() ，然后用它的一个 child 交换置换的值，直到恢复不变量。

同样，push()来电push_back()然后执行一系列交换，尽管方向相反。

注意:由于 C++ 使用最大堆(与常见约定相反)，不变的是任何元素都必须大于它的两个子元素(如果它们存在)。由于大多数有用的问题都涉及最小堆，因此您几乎总是必须指定 std::greater<>作为Compare模板参数。