十、优先级队列
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 once namespace 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 once namespace 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; } }; }
