STL之priority_queue使用简介
2024-08-27 17:15:49
优先队列容器也是一种从一端入队,另一端出对的队列。不同于一般队列的是,队列中最大的元素总是位于队首位置,因此,元素的出对并非按照先进先出的要求,将最先入队的元素出对,而是将当前队列中的最大元素出对。
C++ STL 优先队列的泛化,底层默认采用 vector 向量容器,使得队列容器的元素可做数组操作,从而应用堆算法找出当前队列最大元素,并将它调整到队首位置,确保最大元素出队。
堆算法(heap algorithm) 具有 nLog(n) 阶的算法时间复杂度,优先队列也可看作容器适配器,将底层的序列容器 vector 转换为优先队列 priority_queue.
priority_queue 优先队列容器的 C++ 标准头文件也是 queue ,需要用宏语句 "#include <queue>" 包含进来。
同样是因为仅需取队首和队尾元素的操作,因此 priority_queue 优先队列容器也不提供迭代器,对其他任意位置处的元素进行直接访问操作。使用时,一般用 priority_queue<T> 的形式进行具现, T 是优先队列元素的一个具现类型。
创建 priority_queue 对象
使用 priority_queue 队列之前,要先利用构造函数生成一个优先对象,才可进行元素的入队、出对、取队首及队尾等操作。
1. priority_queue()
默认的构造函数,创建一个空的 priority_queue 对象。例如,下面一行代码使用默认的 vector 为底层容器,创建了一个空的优先队列对象 pq ,数据元素为 int 类型。
priority_queue<int> pq;
2. priority_queue(const priority_queue&)
复制构造函数,用一个优先队列对象创建新的优先队列对象。例如,下面一行代码利用 priority_queue 对象 pq1 ,创建一个以双向链表为底层容器的 priority_queue 对象 pq2 。
// priority_queue<int, list<int> > pq1;
priority_queue<int, list<int> > pq2(pq1);
元素入队
优先队列容器的元素入队函数也是 push 函数,它调用堆算法函数将入队的元素移至队列堆中的正确位置,保证队列优先级高的元素始终位于队首。优先队列也不预设固定的大小,因此 push 函数不判断队列空间是否已满,都将元素放入队列。push 函数不会返回元素入队是否成功的信息。
void push(const value_type& x)
元素出对
优先队列容器的元素出对函数为 pop 函数,将优先级最高的元素删掉。该函数不判断队列是否已为空,都试图将队首元素删除。一般要先判断队列不为空,才进行元素出对操作。
取队首元素
优先队列容器的 top 函数,可用来读取队首元素,即优先级最高的元素。这个函数实际是调用了底层容器的 front 函数。需要注意的是,优先队列容器并不提供获取队尾元素的函数。如下是 top 函数的使用原型。
const value_type& top() const
队列非空判断
优先队列的操作基本都要使用 empty 函数,判断入队和出对的优先队列是否为空,再作下一步的操作。如下是 empty 函数的使用原型。
#include <queue>
#include <iostream>
using namespace std;
int main()
{
priority_queue<int> pq;
pq.push();
pq.push();
pq.push();
pq.push();
pq.push();
// 按优先级大小读取队列元素
while (!pq.empty())
{
// 打印出 33 29 26 19 7
cout << pq.top() << ' ';
pq.pop();
}
cout << endl;
return ;
}
最新文章
- 01 Apache Solr:提升检索体验 为什么是Solr
- Subway Icon Set – 306个像素完美的特制图标
- WebApi接口传参不再困惑(4):传参详解 一、get请求 二、post请求 三、put请求 四、delete请求 五、总结
- 目前比较全的CSS重设(reset)方法总结
- 匿名函数和Lambda表达式
- 8086FLAG寄存器
- poj2777--Count Color(线段树,二进制转化)
- 【网络协议】TCP交互数据流和数据流成块
- HDU5475
- Windows 10安装Docker 步骤及顺序
- Unity more efficient find
- 四:(之七_如何与运行中容器交互)Dockerfile语法梳理和实践
- 团队第二次 # scrum meeting
- Ubuntu16.04搭建QingdaoU(docker一键式部署)
- java线程安全之并发Queue
- Java热部署相关
- python自定义函数和推导
- Spring事务管理要点总结
- ubuntu14下搭建svn
- 转: kali msfvenom生成木马
热门文章
- ELKB是什么?
- app上线
- IIS配置MIME类型
- 洛谷P1968 美元汇率
- BZOJ4198: [Noi2015]荷马史诗(哈夫曼树)
- BZOJ3288: Mato矩阵(欧拉函数 高斯消元)
- LNMP+HAProxy+Keepalived负载均衡 - 基础服务准备
- 使用myeclipse创建servlet后输入地址无法访问
- python__高级 : 动态添加 对象属性, 类属性, 对象实例方法, 类静态方法, 类方法
- PHP实现qq三方登录