共计 2252 个字符,预计需要花费 6 分钟才能阅读完成。
人不知; 鬼不觉 C ++STL 教程系列曾经第 7 期了。之前咱们介绍过:vector
, queue
, stack
, set
, map
等等数据结构。
明天咱们来学习一个新的 stl 容器:priority_queue
优先队列。
🎈 作者:Eriktse
🎈 简介:19 岁,211 计算机在读,现役 ACM 银牌选手🏆力争以通俗易懂的形式解说算法!❤️欢送关注我,一起交换 C ++/Python 算法。(优质好文继续更新中……)🚀
🎈 集体博客:www.eriktse.com
priority_queue 介绍
priority_queue
是 STL 中的一个重要容器,它相似于一般的队列,反对弹出堆顶元素和插入元素的操作,然而有一个很大的不同:队列中元素依照优先级参数排序,最小(或者最大)元素总是在队列的前端,并且会在每次出队的时候被删除。
priority_queue
领有两种不同的形式:一种是依照大顶堆(max heap
)形式排序,另一种是依照小顶堆(min heap
)形式排序。STL 提供了基于容器改编的 priority_queue
,因而能够在传递给priority_queue
的容器中,反对不同类型的元素。
初始化
在应用 priority_queue
之前须要引入头文件#include <priority_queue>
。
用以下代码初始化一个空的priority_queue
。
priority_queue<int> pq;// 默认为大根堆
priority_queue<int, vector<int>, greater<int> > pq2;// 批改为小根堆
能够用适当类型的对象初始化一个优先级队列:
string wrds[] { "one", "two", "three", "four"};
priority_queue<string> words {start(wrds), end(wrds)}; // "two" "three" "one" "four"
如果是寄存构造体,且要自定义比拟函数,能够用 仿函数
,就是用写一个构造体,而后重载()
运算符。
struct Node
{int a, b;};// 申明 Node 构造体
struct cmp
{bool operator () (const Node &u, const Node &v)const
{return u.a < v.a;}
};
priority_queue<Node, vector<Node>, cmp> pq_Node;
罕用操作函数
priority_queue
仅保护一个顶部。
插入元素
push()
办法:用于将一个新元素增加到堆中。
pq1.push(1);// 将元素 1 插入到 pq1 中。
获取堆顶元素
top()
办法:获取堆顶的元素,然而不会自动弹出,如果须要弹出请再加一个pop()
。
留神当堆为空时,不容许获取堆顶元素,或弹出堆顶元素,须要判断堆非空能力对堆顶操作。
获取堆内元素个数
size()
办法:返回一个非负整数,示意堆内元素个数。
当 size() == 0
时,示意堆为空。
判断堆是否为空
empty()
办法:返回一个 bool 值,示意堆是否为空。
cout << pq.empty() << '\n';//true
pq.push(1);
cout << pq.empty() << '\n';//false
弹出元素
pop()
办法:函数用于从堆中弹出以后最大值,并删除该元素。
pq.pop();// 将 pq 中的堆顶元素弹出。
举个例子
#include <iostream>
#include<queue>
using namespace std;
int main()
{
// 以下是字符常量
priority_queue <char> pq;
pq.push('C');
pq.push('Q');
pq.push('T');
pq.push('A');
// 打印队列
cout << "队列中的元素为:" << endl;
while (!pq.empty())
{cout << pq.top() << " ";
pq.pop();// 弹出}
cout << endl;
// 整型变量
priority_queue <int> pq1;
pq1.push(30);
pq1.push(100);
pq1.push(25);
pq1.push(15);
// 打印队列
cout << "队列中的元素为:" << endl;
while (!pq1.empty()) {cout << pq1.top() << " ";
pq1.pop();}
cout << endl;
// 浮点常量
priority_queue <float> pq2;
pq2.push(2.5);
pq2.push(1.6);
pq2.push(103.5);
pq2.push(17.1);
// 打印队列
cout << "队列中的元素为:" << endl;
while (!pq2.empty()) {cout << pq2.top() << " ";
pq2.pop();}
cout << endl;
return 0;
}
总结
priority_queue
的罕用操作方法总结:
1、push()
办法:向优先队列中插入元素,插入的元素的优先级由其权值决定。
2、pop()
办法:从优先队列中弹出最小的元素,将其从队列中删除。
3、top()
办法:获取队列中最小的元素,不会将其从队列中删除。
4、empty()
办法:判断队列是否为空,为空返回 true,不为空返回 false。
5、size()
办法:获取队列中元素的个数。
总的来说,priority_queue
是一种十分有用的容器,它反对不同类型元素的存储和优先级高下排序,对于简略的工作操作,配合几个函数即可实现,而且还能够自定义比拟函数扭转默认的排序形式。