为什么优先队列需要使用底层容器的front()和pop_back()而不是back()和pop_back()呢？

Question

根据 C++ Primer 和 https://en.cppreference.com/w/cpp/container/priority_queue, 我了解到：

一个优先队列除了需要 front、push_back 和 pop_back 操作外，还需要随机访问；

我也阅读了 Google 的这篇博客文章并知道：

• push：将一个新元素添加进队列，
• pop：移除队列中最大的元素，
• top：访问队列中最大的元素。

push 应该通过 push_back 实现，没问题。 而且 pop 和 top 看起来操作的是同一个元素。一个是访问它，另一个则是移除它。因此我认为这两个操作应该由 pop_front() 和 front() 或者 pop_back() 和 back() 实现。

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

例如，假设底层容器是一个vector，并且使用一些int元素，比如1,2,3,4,5,6。适配器接口"pop(), top()"如何与底层"front(), pop_back()"配合工作？

- Rick

---

@Someprogrammerdude 我就是理解不了优先队列接口和底层容器最小操作需求之间的联系。我的意思是，为什么最少需要的是 push_back、pop_back 和 front。（当然，push_back 很容易理解） - Rick

“pop” 用于移除 “top” 元素。因此，我认为底层操作也应该针对同一元素，对吗？比如说一个向量，“pop_back()” 和 “front()” 并不针对同一元素。 - Rick

我认为这是因为优先队列的实现是通过堆来完成的。请参见https://dev59.com/lnA85IYBdhLWcg3wBO7h - unholy_me

Answer 1

尽管在优先队列中，pop() 最终会删除顶部元素，但它必须保持不变式，如果所有元素简单地移动过去，则不会发生这种情况。因此，它通过将来自 front() 的顶部值与 back() 进行交换，并 pop_back() 该值，然后将被替换的值与其子级之一进行交换，直到恢复不变式为止。

同样地，push() 调用 push_back() 然后执行一系列交换，只不过方向相反。

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

- o11c

---

抱歉，我对堆了解不多（ಥ_ಥ）。据我理解，您的意思是：例如，我在一个使用vector实现的优先队列中存储了1,2,3。经过一些排序后，它内部看起来像这样[3][2][1]。当我调用pop时，它会变成[1][2][3]（将顶部值交换到后面），然后弹出[3]，是这样吗？ - Rick

通常情况下，在插入 1, 2, 3 后的顺序将是 3, 1, 2。这是因为在插入 2 后，通过将 2 上移来恢复不变量（我称之为“向上渗透”，类比下面描述的“向下渗透”）：2, 1。然后，您插入 3 并让其向上渗透，所以 2, 1 → 2, 1, 3 → 3, 1, 2（交换 2 和 3）。在删除时，如 @o11c 所说，您交换 front() 和 back()，执行 pop_back()，然后让新的 front() “向下渗透”，所以 3, 1, 2 → 2, 1, 3 → 2, 1（完成，无需让 2 向下渗透，因为它已经大于其（唯一的）子节点）。 - Arne Vogel

@Rick 顺便提一下，你可能想看一下 push_heap 和 pop_heap 的描述。优先队列的 push() 可以实现为 c.push_back() 后跟 push_heap()。优先队列的 pop() 可以实现为 pop_heap() 后跟 pop_back()。还有 make_heap()，在从迭代器范围（或 initializer_list，如果有这样的构造函数）创建pq时很有用 - 先通过从范围复制来创建容器，然后使用 make_heap()。 - Arne Vogel

@ArneVogel，您的详细解释非常有帮助。我已经读了一些关于堆的东西。现在结合您的回答和评论，我对它有了一个模糊的理解。谢谢:D。 - Rick