目录
一、 定义
二、优先队列内元素访问
三、优先队列常用函数
四、优先队列内元素的优先级
优先队列(priority_queue),底层的数据结构为堆(heap),以此保证队首元素一定是当前队列所有元素中优先级最高的。我们也可以随时往优先队里面加入(push)元素,其队首元素依然为优先级最高的。
一、 定义
头文件:#include<queue>
定义的写法与其他STL容器相同,Type可以是任意的基本数据类型或是容器,Container是容器类型(这里必须是用数组实现的容器,例如vector,deque,但是不能使用list,STL里默认是vector),Functional是比较方式(升序队列:大顶堆;降序队列:小顶堆):
priority_queue<Type,Container,Functional> name;
二、优先队列内元素访问
普通队列是先进先出的数据结构,元素在队尾添加,在队头删除。
在优先队列中,当访问元素时,元素被赋以优先级,优先级高的元素先删除,先出队。
优先队列与普通队列的不同在于我们可以定义队列内元素的优先级,通过优先级控制出队顺序。优先队列没有front()函数和back()函数,只能通过top()函数来访问队首元素(即堆顶元素):
#include<iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int> pot;
pot.push(2);
pot.push(6);
pot.push(3);
cout << pot.top() << endl;
return 0;
}
输出结果:6
三、优先队列常用函数
与队列基本操作大致相同:
- push() 插入元素到队尾并排序,时间复杂度为O(logN)
- top() 访问队首元素,时间复杂度为O(1),使用前应先判断优先队列是否为空
- pop 弹出队首元素,时间复杂度为O(logN),使用前应先判断优先队列是否为空
- empty() 判断队列是否为空,时间复杂度为O(1)
- size() 返回队内元素个数,时间复杂度为O(1)
- emplace() 原地构造一个元素并插入队列
- swap() 交换内容
#include<iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int> dsp;
//判断优先队列是否为空
cout << dsp.empty() << endl;
dsp.push(2);
dsp.push(4);
dsp.push(1);
dsp.push(5);
//输出队首元素
cout << dsp.top() << endl;
//弹出队首元素,再输出队顶元素
dsp.pop();
cout << dsp.top() << endl;
//输出优先队列元素个数
cout << dsp.size() << endl;
}
输出结果:
四、优先队列内元素的优先级
像int、double、char等基本数据类型,他们的优先级一般就是数字较大的优先级较高(如果是char型的就是根据字典序大小):文章来源:https://www.toymoban.com/news/detail-567082.html
priority_queue<int> dsp;
priority_queue<int, vector<int>, less<int> > dsp;
priority_queue<int, vector<int>, greater<int> > dsp;
第一种即常见的定义方法,后面两种中多了两个参数,vector<>是用来承载底层堆结构的容器;less<>和greater<>则是第一个参数的比较类,分别表示数字越大优先级越大(大顶堆)、数字越小优先级越高(小顶堆)。文章来源地址https://www.toymoban.com/news/detail-567082.html
到了这里,关于C++优先队列(priority_queue)详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!