优先级队列(Priority Queue)
队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。
1. 优先级队列的概念
优先级队列的定义
优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
优先级队列的特点
- 优先级队列是0个或多个元素的集合，每个元素都有一个优先权或值。
- 当给每个元素分配一个数字来标记其优先级时，可设较小的数字具有较高的优先级，这样更方便地在一个集合中访问优先级最高的元素，并对其进行查找和删除操作。
- 对优先级队列，执行的操作主要有：(1)查找，(2)插入，(3)删除。
- 在最小优先级队列(min Priority Queue)中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素。
- 在最大优先级队列(max Priority Queue)中，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。
- 插入操作均只是简单地把一个新的元素加入到队列中。
- 注：每个元素的优先级根据问题的要求而定。当从优先级队列中删除一个元素时，可能出现多个元素具有相同的优先权。在这种情况下，把这些具有相同优先权的元素视为一个先来先服务的队列，按他们的入队顺序进行先后处理。
2.优先级队列的使用
头文件：#include < queue >
优先级队列默认是最大优先级队列
接口介绍
| 函数声明 |
函数说明 |
| priority_queue() / priority_queue(first, last) |
构造一个空的优先级队列 |
| empty( ) |
判断优先级队列是否为空，为空返回true |
| empty( ) |
判断优先级队列是否为空，为空返回true |
| top( ) |
获取优先级队列中最大或者最小的元素，即堆顶元素 |
| push(x) |
将x元素插入到优先级队列中 |
| pop() |
删除优先级队列中最大或者最小的元素， 即删除堆顶元素 |
测试代码：
void test()
{
priority_queue<int> pq;
pq.push(13);
pq.push(14);
pq.push(9);
pq.push(23);
pq.push(12);
pq.push(22);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
测试结果：默认是最大优先级队列，所以堆顶元素一直是最大的元素
如何将创建最小优先级队列----
优先级队列原型：
泛型介绍：T为优先级队列存储的数据类型；Container为优先级队列中存储数据的容器；Compare伪函数，决定是最大优先级队列还是最小优先级队列
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
创建最小优先级队列：
priority_queue<int, vector<int>, greater<int>> pq;
测试结果：
优先级队列存放自定义类型时，需要自定义类型支持比较的操作。
class A
{
public:
A(int a = 1)
:_a(a)
{}
//支持比较函数
bool operator<(const A& a) const
{
return _a < a._a;
}
bool operator>(const A& a) const
{
return _a > a._a;
}
int _a;
};
测试结果：
GG3F&'22V"c#cf#SC36&F3v33fcS2r##УYhY~h"7&3GG3F&'22V"csC&C#SvCv3fV3F6SSr#У[NK>zУb673&66У&R673''W67#ТZJ~i[{~FVFRf672BfwCЧ7G'V7B70ЧТ&F6Bf6Bf"ТТ&WGW&f#ТРТK[{~FVFRf672BfwCЧ7G'V7Bw&VFW ЧТ&F6Bf6Bf"ТТ&WGW&fwC#ТРЧFVFRf672B6726fV7FCBfwC6726&R72fBfwCfwCЦ672&VWVPЧЧV&3Т K>i[@Тf6gDFТТ&VТ6"&VТv6f6RТТb6f6Rff666ТТ6Тb66&V6ТТ7v6&V6Т&V6Т6"&VТVPТТ'&VТТ K>i[@Тf6gEW6ТТ&V6Тv6fwCТТb66&V6ТТ7v6&V6Т6&VТ&V6ТVPТТ'&VТТfW66BffТТ Т6W6fТ6gEW6RТТfТТNhТ7v66RТ66Т6gDFТТBfFТТ&WGW&&ТТ6UR6ТТ&WGW&RТТ&VG6ТТ&WGW&GТ&fFSТ666&R6Ч&SУFcУjX[>KZ.X&V^yNKyJXxNih~z[ K{NZIyX[42Z.X&V^Xh^Z{J.zKK^XNih~zhn{~{XyNyX[>ih~z[ZJ~Z^YZIiJ | 
转播
