来自 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()
”?
最佳答案
虽然pop()
在 priority_queue
最终删除顶部元素,它必须保持不变量,如果所有元素都简单地移动就不会发生这种情况。因此,它通过交换 front()
中的最高值来工作。至back()
和 pop_back()
,然后用它的一个 child 交换置换的值,直到恢复不变量。
同样,push()
来电push_back()
然后执行一系列交换,尽管方向相反。
注意:由于 C++ 使用最大堆(与常见约定相反),不变的是任何元素都必须大于它的两个子元素(如果它们存在)。由于大多数有用的问题都涉及最小堆,因此您几乎总是必须指定 std::greater<>
作为Compare
模板参数。
关于c++ - 为什么优先级队列需要底层容器的front()、pop_back()而不是back()、pop_back()?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51017198/