priority_queue
作者:
qpalzmczy
,
2024-04-06 12:09:18
,
所有人可见
,
阅读 61
priority_queue 是 C++ 标准模板库(STL)中的一个容器适配器,它提供了队列的行为,但是以优先级为基础进行元素的排序。在 priority_queue 中,每次从队列中取出的总是当前队列中优先级最高的元素。
priority_queue 默认是一个最大堆,也就是说,最大的元素总是位于堆顶。如果你想要一个最小堆,可以通过传递一个比较函数来改变排序准则。
以下是 priority_queue 的一些基本用法:
创建和初始化:
std::priority_queue<int> pq; // 默认最大堆
std::priority_queue<int, std::vector<int>, std::greater<int>> pq_greater; // 最小堆
基本操作:
push:将元素添加到堆中。
pq.push(1);
pq.push(3);
pq.push(2);
pop:移除堆顶元素,即优先级最高的元素。
int top_element = pq.top(); // 获取堆顶元素但不移除
pq.pop(); // 移除堆顶元素
top:访问堆顶元素,不移除。
int top_element = pq.top();
empty:检查堆是否为空。
bool is_empty = pq.empty();
size:获取堆中元素的数量。
size_t size = pq.size();
使用场景:
Dijkstra 算法:用于图论中的最短路径算法,priority_queue 可以用来存储待处理的顶点和它们的最短估计距离。
堆排序:priority_queue 可以用来实现堆排序,通过反复地移除堆顶元素并重建堆来对数组进行排序。
调度任务:在操作系统中,可以使用 priority_queue 来管理进程或任务,根据它们的优先级来调度执行。
注意事项:
priority_queue 不支持随机访问,也不能直接访问堆中的元素。
priority_queue 的元素一旦被弹出,就无法再次被推入,因为堆的结构可能会因此改变。
priority_queue 的内部顺序是不确定的,因为它依赖于堆的实现。