---

十、优先级队列

1. priority_queue的介绍

优先级队列 其实也不属于队列，它跟 stack 和 queue 一样，都是 容器适配器 。

优先级队列的默认适配容器是 vector 。要使用优先级队列的话，需要包含 queue 头文件 。

优先级队列的接口也非常简单明了，我们来简单试一下：

#include<iostream>
// 包含 queue 头文件
#include<queue>
using namespace std;int main()
{priority_queue<int> pq;pq.push(3);pq.push(1);pq.push(4);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

我们插入的数据是 3 1 4 2 ，打印出来的数据却是 4 3 2 1 ，竟然将其排了个降序，这有点像我们之前学过的一种数据结构啊。是的，它很像 堆，它底层其实就是 大根堆 。优先级队列 就是按优先级取数据，堆顶数据就是优先级最高的。

2. 优先级队列如何使小的数据优先级高

优先级队列默认是大根堆，大的数据优先级高，那么我们该如何使小的数据优先级高呢？就是使优先级队列以 小根堆 的形式实现。答案嘛，就涉及到 STL 的另一个组件了—— 仿函数 。

优先级队列 模板的第三个参数就是仿函数，默认是 less （小于），如果要使其成 小根堆 的形式，则需要将其参数修改为 greater （大于），由于缺省参数不能跳跃着传，所以需要将前面两个参数都给加上才行。

// 三个参数
priority_queue<int, vector<int>, greater<int>> pq;

我们来使用一下：

#include<iostream>
#include<queue>
using namespace std;int main()
{priority_queue<int, vector<int>, greater<int>> pq;pq.push(3);pq.push(1);pq.push(4);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

在其他有这种仿函数的函数中，less 默认都是排升序 ，greater 都是排降序 ，比如 sort 函数 ，而 优先级队列 中，less 是大根堆 ， greater 是小根堆 。

// sort 排降序
sort(v.begin(), v.end(), greater<int>());

注意，sort 函数 的第三个参数是函数参数，需要传对象，所以末尾带着 () 来创建匿名对象，而 优先级队列 则是类模板，传类型，不需要带 () 。

3. 仿函数介绍

仿函数其实是一个类型 ，一种结构。

struct Less
{// 重载 ()bool operator()(const int& x, const int& y){return x < y;}
};

我们要怎样使用这个类呢？

int main()
{Less Lessfunc;cout << Lessfunc(1, 2) << endl;// 上面写法本质上是下面写法cout << Lessfunc.operator()(1, 2) << endl;return 0;
}

大家有没有发现，上面的写法 很像函数 啊，Lessfunc 就像函数名一样，但是没想到其实他是对象名。所以 仿函数就是对象很像函数的类型 。把模板套上就可以使类型泛型。

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

所以在 sort 函数 里的第三个参数，greate< int >() 就是一个匿名对象，类型是 int ，调用重载 () 符号。

4. priority_queue的模拟实现

先把简单的框架搭好，再来挨个实现。由于 STL库 里的 priority_queue 是位于 queue 头文件里，所以我们这里头文件取名为 Queue.h 。

// Queue.h
#pragma oncenamespace my
{template<class T, class Container = vector<T>>class priority_queue{public:void push(const T& x){}void pop(){}bool empty(){}size_t size(){}const T& top(){}private:Container _con;};
}

我们来想一想，我们的堆是如何插入数据的：堆是尾部插入数据，然后向上调整位置 。那堆是如何删除数据的呢？堆是收尾交换数据，然后尾删，最后将堆顶数据向下调整 。

#pragma oncenamespace my
{template<class T, class Container = vector<T>>class priority_queue{public:adjust_up(size_t child){}adjust_down(size_t parent){}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};
}

向上调整函数注意的就是什么情况可以向上调整，当孩子的值比父亲大时，需要将孩子的位置与父亲的位置进行交换 ，然后更新孩子和父亲的下标。那什么时候结束调整呢？当孩子的值比不父亲的值大，或者孩子已经到堆顶位置 此时需要结束调整。

adjust_up(size_t child)
{size_t parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){// 交换数据std::swap(_con[child], _con[parent]);// 更新下标child = parent;parent = (child - 1) / 2;}else{ break;}}
}

向下调整需要注意的是，父节点要是最大的值，所以要交换也是与最大的孩子交换，第一步需要找到最大的孩子 ，然后 判断父亲是否比孩子小，小则交换，最后判断结束条件 父节点已经不再比最大的孩子小或者，已经到达叶子节点 则退出。

adjust_down(size_t parent)
{size_t child = parent * 2 + 1;// 左孩子孩子存在while (child < _con.size()){// 右孩子存在且比左孩子大if (child + 1 < _con.size() && _con[child + 1] > _con[child]){++child;}if (_con[parent] < _con[child]){// 交换std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

除了仿函数外，我们的代码已经实现到了：

// Queue.h
#pragma once
#include<vector>
namespace my
{template<class T, class Container = vector<T>>class priority_queue{public:void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{ break;}}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){++child;}if (_con[parent] < _con[child]){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};
}

// test.cpp
#include<iostream>
#include"Queue.h"
using namespace std;int main()
{my::priority_queue<int> pq;pq.push(1);pq.push(3);pq.push(4);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

OK，这里默认大堆就已经完成了。但是我们这个代码并不能控制变成小堆，我们需要 使用仿函数来控制比较逻辑 。

// 在 my 命名空间内
template<class T>
class less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};

有了仿函数，所以我们的优先级队列模板参数就要将其加上。

// 默认大根堆，第三个参数默认是仿函数 less
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public://
private://
};

所以，类里的比较大小的判断就可以使用仿函数来调用对象来实现。

void adjust_up(size_t child)
{// 这里Compare com;size_t parent = (child - 1) / 2;while (child > 0){// _con[parent] < _con[chlid]if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{ break;}}
}void adjust_down(size_t parent)
{// 这里Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){// _con[child] < _con[child + 1]if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//_con[parent] < _con[child]if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

测试一下：

#include<iostream>
#include"Queue.h"
using namespace std;int main()
{// 大堆my::priority_queue<int> pq;pq.push(1);pq.push(3);pq.push(4);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;// 小堆my::priority_queue<int, vector<int>, greater<int>> pq2;pq2.push(1);pq2.push(3);pq2.push(4);pq2.push(2);while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;return 0;
}

可以。

补： 反向迭代器

反向迭代器其实可以通过修改正向迭代器来达到目的，但是我们要求代码复用，所以需要用另一种方法来实现反向迭代器。此时我们可以使用 迭代器适配器 来实现所有容器的反向迭代器。你给我一个容器的正向迭代器，我来帮你实现其反向迭代器。

反向迭代器和正向迭代器的不同点在哪？功能类似，++和–方向不一样 。
其中反向迭代器的模板部分代码就如下所示，只需要注意反向迭代器要正确调用正向迭代器的函数就能成功实现。比如：++调用–，–调用++。

#pragma once
namespace me
{template<class Iterator, class Ref, class Ptr>class ReverseIterator{public:typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator _it;ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}// 前置++Self& operator++(){--_it;return *this;}// 前置--Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}};
}

---

未完待续