$priority\_queue$ 是一种容器适配器，设计为大根堆（默认）这个数据结构。优先队列是一个拥有权值观念的 $queue$，因此，其只能在底端入元素，顶端出元素，其内的元素自动按照元素的权值排列，权值高者排在最前面。因此，根据堆结构得知，其需要一个具有随机访问迭代器的容器（$vector$）加上实现大根堆原理的算法（$max-heap$）。和 $queue$ 的原理相同，优先队列不允许有遍历行为（只能取堆顶元素），因此没有迭代器。

---

前言 —— 容器适配器

适配器是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结），该种模式是将一个类的接口转换成客户希望的另外一个接口。

---

一、priority_queue 的介绍

关于 $priority\_queue$ 的介绍，建议去查 $C$++ 官方文档：$priority\_queue$ 的文档介绍。

以下为 $priority\_queue$ 的官方文档介绍：

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的（大根堆）。

2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中位于顶部的元素）。

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，$queue$ 提供一组特定的成员函数来访问其元素。元素从特定容器的 $“$尾部$”$ 弹出，其称为优先队列的顶部。

4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过
   随机访问迭代器访问，并支持以下操作：
   (1)empty()：检测容器是否为空。
(2)size()：返回容器中有效元素个数。
(3)front()：返回容器中第一个元素的引用。
(4)push_back()：在容器尾部插入元素。
(5)pop_back()：删除容器尾部元素。

5. 标准容器类 $vector$ 和 $deque$ 满足这些需求。默认情况下，如果没有为特定的 $priorit{y}_{q}ueue$ 类实例化指定容器类，则使用 $vector$。

6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 $make\_heap$、$push\_heap$ 和 $pop\_heap$ 来自动完成此操作。

优先队列结构：

底层结构（堆）：

---

二、priority_queue 的使用（常用接口）

下面只列举了 $priority\_queue$ 最核心的接口，更多详细信息可以自行查官方文档：$priority\_queue$。

$priority\_queue$ 的第二个模板参数不是 alloc 而是 Container，说明其为容器适配器，缺省值为 $vector$ 说明标准库里的 $priority\_queue$ 默认的底层容器为为 $vector$。

$$\begin{gathered} template<classT,classContainer=vector<T>, \\ classCompare=less<typenameContainer::value\_type>>classpriority\_queue; \end{gathered}$$

其第三个参数为仿函数，默认为 less<T> 小于比较逻辑（大根堆）。

函数说明	接口说明
$priority\_queue()$	构造一个空的优先级队列
$empty()$	检测优先级队列是否为空，是返回 $true$，否则返回 $false$
$top()$	返回优先级队列中最大（最小）元素，即堆顶元素
$push(x)$	在优先级队列中插入元素 $x$
$pop()$	删除优先级队列中最大（最小）元素，即堆顶元素

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

【注意】

1. 默认情况下，$priority\_queue$ 是大根堆：

#include <vector>
#include <queue>
#include <functional> // greater算法的头文件void TestPriorityQueue()
{// 默认情况下，创建的是大堆，其底层按照 < 比较vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> q1;for(auto& i : v) q1.push(i);cout << q1.top() << endl;	// 9// 如果要创建小堆，将第三个模板参数换成greater比较方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;	// 0
}

2. 如果在 $priority\_queue$ 中放自定义类型的数据，用户需要在自定义类型中提供 $>$ 或者 $<$ 的重载。

以之前写过的日期类为例：

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _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;}
private:int _year;int _month;int _day;
};void TestPriorityQueue()
{// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;	// 2018-10-30// 如果要创建小堆，需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout << q2.top() << endl;	// 2018-10-28
}

---

三、仿函数（functors）

仿函数：本质是一个类，这个类重载了 $operator()$，它的对象可以像函数一样使用。

仿函数在 $STL$ 的历史上有两个不同的名称：

1. 仿函数（$functors$）是早期的命名。

2. $C$++ 标准规格定案后所采用的新名称是函数对象（$functionobjects$）。

就实现意义而言，函数对象比较贴切：一种具有函数特质的对象。

不过就行为而言，仿函数一词比较突出：在调用的时候，可以像函数一样被调用；在被调用的时候，则以对象所定义的回调函数操作（$functioncalloperator$）扮演函数的实质角色。

因此，我更喜欢将其叫做仿函数。

仿函数其实就是一个模板类，示例如下：

1. 定义一个小于 $<$ 逻辑的仿函数类：

template<class T>
class Less
{
public:bool operator () (const T& x, const T& y){return x < y;}
};

2. 定义一个大于 $>$ 逻辑的仿函数类：

template<class T>
class Greater
{
public:bool operator () (const T& x, const T& y){return x > y;}
};

测试一下：

void test1()
{Less<int> LessFunc;Greater<int> GreaterFunc;//函数对象LessFunc(1,2) == true ? cout << "1 < 2" << endl : cout << "false <" << endl;//本质是：LessFunc.operator()(1,2)GreaterFunc(1,2) == true ? cout << "1 > 2" << endl : cout << "false >" << endl;//本质是：GreaterFunc.operator()(1,2)
}

那么仿函数具体有什么应用呢？

以排序算法中的冒泡排序（$BubbleSort$）为例，默认为升序排序：

void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int flag = 0;for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j]){swap(a[j - 1], a[j]);flag = 1;}}if (flag == 0)break;}
}

与此同时就产生了一个问题：

这个排序只能适用于升序排序，被定死了，怎么稍作修改就能将其改造成一个降序排序呢？

此时就要使用到 —— 仿函数，让仿函数作为类模板的形式给排序加一个新参数，这样就方便修改了：

template<class Compare>
void BubbleSort(int* a, int n, Compare com)
{for (int i = 0; i < n - 1; i++){int flag = 0;for (int j = 1; j < n - i; j++){//注意：这里要满足仿函数的比较逻辑需要将两元素换一下位置if (com(a[j], a[j - 1]))	//把比较逻辑交给仿函数去实现{swap(a[j - 1], a[j]);flag = 1;}}if (flag == 0)break;}
}

测试一下：

void test2()
{Less<int> LessFunc;Greater<int> GreaterFunc;int a[] = { 9,1,2,5,7,4,6,3 };//升序BubbleSort(a, 8, LessFunc);//BubbleSort(a, 8, Less<int>()); //可以传匿名对象for (int i = 0; i < 8; i++) cout << a[i] << " "; cout << endl;//降序BubbleSort(a, 8, GreaterFunc);//BubbleSort(a, 8, Greater<int>()); //可以传匿名对象for (int i = 0; i < 8; i++) cout << a[i] << " "; cout << endl;
}

因此，我们也可以看到标准库中的 $sort$ 算法也给了第三个模板参数，可以传仿函数：

这样就能够自定义比较逻辑，想升序就填 less<T>，想降序就填 greater<T>，非常便利和灵活。

注意：以上可以看出，仿函数和函数指针的功能类似：都可以达到将整组操作当作算法的参数，那又何必有所谓的仿函数呢？

原因在于：函数指针毕竟不能满足 $STL$ 对抽象性的要求，也不能满足软件积木的要求 —— 函数指针无法和 $STL$ 其他组件（如配接器 $adapter$）搭配，产生更灵活的变化。

在 $C$ + 标准库 $STL$ 中，对于仿函数的分类，可以根据操作数（$operand$）的个数划分，可分为两类：

1. 一元仿函数（$unary\_function$）

2. 二元仿函数（$binary\_function$）

也可以按照功能划分，可分为三大类：

1. 算术运算（$Arithmetic$）

2. 关系运算（$Relational$）

3. 逻辑运算（$Logical$）

想要使用 $STL$ 内建的仿函数，都必须含有 < $functional$ > 头文件，下面以功能划分来介绍常用的仿函数：

1. 算术运算类（Arithmetic）

$STL$ 内建的算术运算类仿函数，支持加法、减法、乘法、除法、取模（余数，$modulus$）和否定（$negation$）运算。除了否定运算为一元运算，其他都是二元运算。

算术运算名	仿函数名
加法	$plus<T>$
减法	$minus<T>$
乘法	$multiplies<T>$
除法	$devides<T>$
取模（$modulus$）	$modulus<T>$
否定（$negation$）	$negate<T>$

2. 关系运算类（Relational）

$STL$ 内建的关系运算类仿函数，支持了等于、不等于、大于、大于等于、小于和小于等于六种运算。每一个都是二元运算。

关系运算名	仿函数名
等于（$equality$）	$equal\_to<T>$
不等于（$equality$）	$not\_equal\_to<T>$
大于（$greaterthan$）	$greater<T>$
大于等于（$greaterthanorequal$）	$greater\_equal<T>$
小于（$lessthan$）	$less<T>$
小于等于（$lessthanorequal$）	$less\_equal<T>$

3. 逻辑运算类（Logical）

$STL$ 内建的逻辑运算类仿函数，支持了逻辑运算中的 $And$、$Or$、$Not$ 三种运算。其中 $And$ 和 $Or$ 为二元运算，$Not$ 为一元运算。

逻辑运算名	仿函数名
逻辑运算 $And$	$logical\_and<T>$
逻辑运算 $Or$	$logical\_or<T>$
逻辑运算 $Not$	$logical\_not<T>$

一般来说，仿函数不需要自己实现，用标准库里的就很好，需要自己实现仿函数的场景主要有：

1. 类类型不支持比较大小。

2. 类类型支持比较大小，但是比较逻辑不是你想要的。

---

四、priority_queue 的模拟实现

$priority\_queue$ 的底层结构就是堆，因此此处只需对其进行通用的封装即可。

如果忘记了堆这个数据结构，可以看看我之前的博客复习一下：【数据结构】堆。

#include<vector>
#include<functional>using namespace std;namespace ybc
{// 默认适配容器为vector, 默认仿函数为lesstemplate<class T, class Container = vector<T>, class Compare = less<T>>	class priority_queue{public:// 向上调整算法void AdjustUp(size_t child){Compare com;	// 创建仿函数对象size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child]))	// 用仿函数实现比较逻辑{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}// 向下调整算法void AdjustDown(size_t parent){Compare com;	// 创建仿函数对象size_t n = _con.size();size_t child = parent * 2 + 1;while (child < n){// 用仿函数实现比较逻辑if (child + 1 < n && com(_con[child], _con[child + 1]))	{child = child + 1;}if (com(_con[parent], _con[child]))	// 用仿函数实现比较逻辑{swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void pop(){swap(_con.front(), _con.back());_con.pop_back();AdjustDown(0);}const T& top(){return _con.front();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

---

总结

由于 $priority\_queue$ 完全以底部容器为根据，再加上 $heap$ 处理规则，所以其实现非常简单，默认情况下是以 $vector$ 为底部容器。

$queue$ 以底部容器完成其所有工作。具有这种 $“$修改某物接口，形成另一种风貌$”$ 的性质者，称为 $adapter$（适配器），因此，$STL$ $priority\_queue$ 往往不被归类为 $container$（容器），而被归类为 $containeradapter$（容器适配器）。