【C++】优先级队列priority_queue

优先级队列priority_queue：

初识优先级队列

1. 优先级队列是一种容器适配器，根据标准默认，它的第一个元素总是它所包含的元素中最大的
2. 优先级队列的本质就是对堆进行操作，堆中可以随意的插入元素，并且只能检索最大的对元素（类似于优先队列的顶部元素）
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。
4. 标准容器类vector和deque满足这些需求，默认的情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

priority_queue的使用

优先级队列默认使用vector作为其底层存储数据结构的容器，在vector上又使用了堆算法将vector中的元素构造成了堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以优先考虑使用priority_queue。但是默认情况下**，priority_queue是大堆**。

函数声明	接口声明
priority_queue(const Compare& x = Compare(), const Container& y =
Container() );	构造一个空的优先级队列
priority_queue (InputIterator first, InputIterator last,const Compare& comp = Compare(),const Container& ctnr = Container());	用迭代器[first,last)区间的元素构造优先级队列
bool empty()	优先级队列是否为空
const value_type& top() const	返回优先级队列中的最大或者最小的元素（大堆堆顶元素或者小堆堆顶元素）
void push(const T& x)	向优先级队列中插入x（向堆中插入元素x，还保证原有堆形态不变）
void pop()	删除优先级队列中堆顶元素（最大的或者是做小的元素）

通过代码进一步理解优先级队列：

#include <iostream>  // std::cout
#include <queue>     // std::priority_queue
#include <vector>    // std::vector
#include <functional>// std::greater
using namespace std;


int main()
{
	vector<int> v = { 40, 20, 60, 50, 30 };
	priority_queue<int> pq1(v.begin(), v.end());//通过迭代器区间构造优先级队列pq1
	// 默认情况下，建的堆是大堆，底层按照<进行比较
	// 所以输出堆顶的最大值 60
	cout << pq1.top() << endl; 

	// 建小堆 将第三个模板参数换成greater
	//  底层按照 > 进行比较
	// 输出的是堆顶的最小值 20
	priority_queue<int, vector<int>, greater<int>> pq2(v.begin(), v.end());
	cout << pq2.top() << endl;

	system("pause");
}

结果：

说明：
默认情况下优先级队列建的都是大堆，即堆顶是最大的数据。priority_queue pq将相当于prority_queue<int,vector< int >,less< int >> pq;
但是，当你需要建小堆的时候就必须将第三个模板参数的less换成greater。 即priority_queue<int,vector< int >,greater< int >> pq;

优先级队列使用的场景

在一些OJ题中，我们也时常需要优先级队列建的堆来完成一些操作。比如什么寻找第K个数了，只要与查找、指定数字K、等等有关的情况都可以考虑优先级队列。
这里有几道OJ题的链接，不妨尝试一下，小练一下。

• 第三大的数：https://leetcode-cn.com/problems/third-maximum-number/
• 数组中第K个最大的元素：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
• 前K个高频元素：https://leetcode-cn.com/problems/top-k-frequent-elements/

总结：

优先级队列其实就是queue队列的接口，其实我们只需要学会queue和理解堆结构，我们就可以更快的掌握优先级队列。

我们也可以通过反问的方式问自己什么是优先级队列，通过反问的方式来弄清楚自己是否理解， 比如：
优先级队列实现的是什吗？ 实现的是一个大堆序列或者小堆序列。为什么要优先级队列的底层实现的是堆结构？因为需要一个容器来完成具有堆特性的操作，比如topk问题，方便完成查找指定数字K的问题。所以我们遇到这类问题要先考虑是否能用到优先级队列，简单处理问题。