C++之priority_queue(最大值优先级队列、最小值优先队列)

C++之priority_queue(最大值优先级队列、最小值优先队列)

文章目录

前言

1、最大值优先级队列、最小值优先级队列
2、优先级队列适配器 STL priority_queue

一、优先级队列

优先队列容器与队列一样,只能从队尾插入元素,从队首删除元素。但是它有一个特性,就是队列中最大的元素总是位于队首,所以出队时,并非按照先进先出的原则进行,而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序,可以重载“<”操作符来重新定义比较规则。

优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue,因为list的迭代器不是任意存取iterator,而pop中用到堆排序时是要求randomaccess iterator 的!):
priority_queue<vector, less > pq1;     // 使用递增less函数对象排序
priority_queue<deque, greater > pq2;   // 使用递减greater函数对象排序
默认情况下是最大值优先队列,也就是递增

二、用法

1、pq.empty();
2、pq.size();
3、pq.top();
4、pq.pop();
5、pq.push(item);

三、用法案例

void main()
{ 
 priority_queue<int> p1;//默认情况下是最大值优先队列
 priority_queue<int,vector<int>,less<int>>  p2;//最大值优先队列
 priority_queue<int,vector<int>,greater<int>> p3;//最小值优先队列

 p1.push(33)l
 p1.push(11);
 p1.push(44);
 p1.push(22);
 while(p1.size()>0)
 { 
	cout<<p1.top()<<" ";//输出队头元素
 	p1.pop();//让队头元素出栈
 }
 结果: 44  33  22  11
 如果用p3完成上述操作的话
 结果: 11  22  33  44
    原文作者:悟道xn
    原文地址: https://blog.csdn.net/Xiao_qsn/article/details/115363086
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞