std::priority_queue
是 C++ 标准库中的一个容器适配器,它提供了一种特殊的队列,其中元素按照优先级进行排序。在这个队列中,元素的优先级可以通过比较函数来确定。默认情况下,优先级最高的元素(最大的元素)会被放在队列的前面。
std::priority_queue
通常使用堆(heap)这种数据结构来实现。堆是一种特殊的二叉树,其中每个节点都有一个值,并且满足堆属性:在最大堆中,每个节点的值都大于或等于其子节点的值;在最小堆中,每个节点的值都小于或等于其子节点的值。
std::priority_queue
提供了以下主要操作:
push()
: 向队列中添加一个元素。pop()
: 删除优先级最高的元素(队列的第一个元素)。top()
: 返回优先级最高的元素,但不删除它。empty()
: 检查队列是否为空。size()
: 返回队列中的元素数量。注意,std::priority_queue
并不支持随机访问迭代器,因此你不能直接访问队列中的任意元素。如果你需要这样的功能,可以考虑使用其他数据结构,如 std::set
或 std::multiset
。
这是一个简单的 std::priority_queue
示例:
#include<iostream>
#include<queue>
int main() {
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);
pq.push(2);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
return 0;
}
输出:
5 3 2 1
这个示例中,我们创建了一个 std::priority_queue
,然后向其中添加了四个整数。当我们从队列中取出元素时,它们按照优先级从高到低的顺序被取出。