优先级队列— priority_queue详细解说以及使用

59 阅读 0 评论 39 点赞

我是靠谱客的博主谨慎绿茶，最近开发中收集的这篇文章主要介绍优先级队列— priority_queue详细解说以及使用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

priority_queue介绍

之前所说的队列，是按照给的顺序逐一入队，而这里要说的优先级队列，底层实现是通过堆来实现的，优先级队列，顾名思义，在入队的时候，就会按照数据大小拍好序来入队，在默认情况下，优先级队列的实现是通过大堆来实现的。具体的概念如下：
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：——检测容器是否为空
size()：——返回容器中有效元素个数
front()：——返回容器中第一个元素的引用
push_back()：——在容器尾部插入元素
函数声明接口说明
priority_queue()/priority_queue(ﬁrst, last)——构造一个空的优先级队列
empty( )——检测优先级队列是否为空，是返回true，否则返回 false
top( ) ——返回优先级队列中最大(最小元素)，即堆顶元素
push(x) ——在优先级队列中插入元素x
pop() ——删除优先级队列中最大(最小)元素，即堆顶元素
pop_back()：——删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。

优先级队列的使用

1.基本使用

#include<queue>
#include<iostream>
#include<vector>
#include <functional>   // greater算法的头文件
usiang namespace std;
void test()
{
	priority_queue<int> pq1;//创建一个int型的空优先队列pq1
	 vector<int> v{3,2,7,6,0,4,1,9,8,5}; 
	 for (auto& e : v)        
	 	pq1.push(e);//元素依次入队
	 // 如果要创建小堆，将第三个模板参数换成greater比较方式    
	 priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());//底层通过小堆来实现
	 cout << q2.top() << endl; 
}
int main()
{
	test()
}
优先级队列的常用接口与queue的接口用法类似，这里就不再讲解

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

#include<iostream>
#include<queue>
#include<functional>
using namespace std;
class date
{
public:
	date(int year,int month,int day)
		:_year(year)
		,_month(month)
		,_day(day)
		{}
	 bool operator<(const Date& d)const//<运算符重载
	 {        
	 	return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);
	 }
	 bool operator>(const Date& d)const//>运算符重载
	 {        
	 	return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);
	 }
 
	 friend ostream& operator<<(ostream& _cout, const Date& d)//输出运算符重载
	 {        
		 _cout << d._year << "-" << d._month << "-" << d._day;        
	 	return _cout;    
	 }
 pubilc:
 	int _year;
 	int _month;
 	int _day;
};
void test()
{
	//底层默认大堆实现，应提供<重载
	priority_queue<date> pq;
	pq.push(date(1999,11,25);
	pq.push(date(2000,12,1);
	pq.push(date(2001,1,1);
	pq.push(date(1997,7,29);
	pq.push(date(2000,7,29)
	//若想小堆实现，则提供>重载
	priority_queue<date，greater<date>> pq1;
	pq1.push(date(1999,11,25);
	pq1.push(date(2000,12,1);
	pq1.push(date(2001,1,1);
	pq1.push(date(1997,7,29);
	pq1.push(date(2000,7,29)
}