admin管理员组文章数量:1624318
在C++标准库中,priority_queue
是一个容器适配器,它提供了队列的所有基本操作,包括元素的入队(push
)和出队(pop
),但是出队操作(top
和 pop
)总是返回(并移除)优先级最高的元素。默认情况下,priority_queue
使用 std::vector
作为底层容器,并使用 std::less
作为比较对象,因此它实现了一个最大堆。
priority_queue
的典型声明如下:
std::priority_queue<T, Container, Compare> pq;
T
是队列中元素的类型。Container
是用来存储元素的底层容器类型,默认为std::vector<T>
。Compare
是一个二元谓词,用于比较队列中的元素,以确定它们的优先级。默认为std::less<T>
,这意味着较大的元素具有更高的优先级。
对于最大堆,你不需要显式指定 Container
和 Compare
,因为默认设置就是你想要的。但是,如果你想实现一个最小堆(即优先级最低的元素先出队),你需要提供一个不同的比较对象,如 std::greater<T>
。
以下是一些 priority_queue
的基本操作:
push(const value_type& val)
: 将元素添加到队列中。top()
: 返回队列中优先级最高的元素(但不移除它)。pop()
: 移除队列中优先级最高的元素。empty() const
: 如果队列为空,则返回true
。size() const
: 返回队列中元素的数量。
下面是一个简单的 priority_queue
使用示例,展示了如何创建最大堆,并向其中添加元素、获取顶部元素和删除元素:
#include <iostream>
#include <queue> // 包含priority_queue的定义
int main() {
std::priority_queue<int> pq; // 创建一个int类型的最大堆
// 向优先队列中添加元素
pq.push(3);
pq.push(1);
pq.push(4);
// 输出并删除最高优先级的元素
while (!pq.empty()) {
std::cout << pq.top() << ' '; // 输出当前最高优先级的元素
pq.pop(); // 删除最高优先级的元素
}
return 0;
}
输出将是:
4 3 1
因为这是一个最大堆,所以数字 4
(具有最高优先级)首先被输出和删除,然后是 3
,最后是 1
。
如果你想要实现一个最小堆,你可以这样声明 priority_queue
:
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
现在,pq
将会按照升序排列元素,因此 top()
操作将返回最小的元素,而 pop()
操作将移除最小的元素。
本文标签: 大堆最小priorityqueue
版权声明:本文标题:C++ priority_queue 最大堆、最小堆的实现 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728895013a1178297.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论