目录
一.认识priority_queue
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
二. priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
| 函数声明 | 接口说明 |
| priority_queue()/priority_queue(first,last) | 构造一个空的优先级队列 |
| empty( ) | 检测优先级队列是否为空，是返回true，否则返回 false |
| top( ) | 返回优先级队列中最大(最小元素)，即堆顶元素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中最大(最小)元素，即堆顶元素 |
测试：
#include<queue> #include<iostream> using namespace std; int main() { //够一个空的优先级队列 priority_queue<int> pri_q; //插入数据 pri_q.push(2); pri_q.push(27); pri_q.push(25); pri_q.push(244); pri_q.push(212); pri_q.push(9); //连续取出堆顶数据打印 while (!pri_q.empty()) { cout << pri_q.top()<<' '; pri_q.pop(); } return 0; }
编辑
三.仿函数
如果我们像控制优先级队列是大堆排，还是小堆排，就需要我们使用放仿函数去控制。
1.什么是仿函数
首先仿函数是一个类，它重载了括号运算符，在使用的时候，定义出对象，就像函数一样使用。
例如：
//仿函数 template<class T> struct Add { int operator()(int e1, int e2) { return e1 + e2; } }; int main() { Add<int> add; cout << add(10, 20) << endl; return 0; }
编辑
2.控制大小堆
在头文件<functional>中包含了两个仿函数,less和granter。
less是判断小于的仿函数，对应堆排出来是大堆，granter是判断大于的仿函数，对应堆排出来是小堆。
#include<queue> #include<functional> #include<iostream> using namespace std; int main() { //小堆 priority_queue<int,vector<int>,greater<int>> small_q; //插入数据 small_q.push(2); small_q.push(27); small_q.push(25); small_q.push(244); small_q.push(212); small_q.push(9); //连续取出堆顶数据打印 while (!small_q.empty()) { cout << small_q.top()<<' '; small_q.pop(); } cout << endl; //大堆 priority_queue<int, vector<int>, less<int>> big_q; //插入数据 big_q.push(2); big_q.push(27); big_q.push(25); big_q.push(244); big_q.push(212); big_q.push(9); //连续取出堆顶数据打印 while (!big_q.empty()) { cout << big_q.top() << ' '; big_q.pop(); } return 0; }
编辑
3.TopK问题
这个问题我们在数据结构二叉树堆的部分已经详细的分析了，感兴趣的可以去看看：数据结构---二叉树---堆
四.模拟实现priority_queue
1.priority_queue的主要接口框架
template<class T, class Continer = vector<T>> class Priority_queue { public: //插入数据 void push(const T& val) { _con.push_back(val); //向上调整 adjust_up(_con.size() - 1); } //删除数据 void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); //向下调整 adjust_down(0); } //返回栈顶数据 const T& top() { return _con[0]; } //判断栈是否为空 bool empty() { return _con.empty(); } private: Continer _con;//适配容器，默认是vector };
2.堆的向上调整算法
编辑
堆的插入需要保证插入以后还是一个堆，所以这里用到了向上调整算法。
在数组中就是，插入一个数在数组的尾上，再通过向上调整算法，调整到合适的位置。
在以堆的角度来看（小堆）为例，将新插入的值看作孩子与其父亲位置的值比较，如果比父亲位置的值还要小，那就将该值与父亲位置的值进行交换，交换后将父亲位置当作新的孩子，继续与其父亲位置的值比较，这样一直向上比较并交换，直到父亲位置的值比自己小或该位置已经没有父亲了，调整结束。
编辑
//向上调整算法 void adjust_up(size_t child) { //1.计算父亲 size_t parent = (child - 1) / 2; while (child > 0) { //如果孩子比父亲大，就交换，否则就直接推出 if (_con[parent]< _con[child]) { swap(_con[parent], _con[child]); //交换之后，父亲成为新的孩子，继续算新的父亲，直到没有孩子了 child = parent; parent = (child - 1) / 2; } else { break; } } }
3.堆的向下调整算法
向下调整算法（大堆为例）:从第一个结点开始，找到其孩子结点中较大的一个与父亲位置进行交换，然后将孩子作为新的父亲，再次比较和交换，直到父亲结点比两个结点的值都大或者已经没有孩子了为止。
//向下调整 void adjust_down(size_t parent) { //计算出左孩子 size_t child = parent * 2 + 1; while (child < _con.size()) { //判断是否有右孩子，右孩子是否比左孩子大 if (child + 1 < _con.size() && _con[child]< _con[child + 1]) { child++; } //较大的孩子如果比父亲大就交换，否则就直接退出循环 if (_con[parent]< _con[child]) { swap(_con[child], _con[parent]); } else { break; } //孩子成为新的父亲，继续算出新的孩子 parent = child; child = parent * 2 + 1; } }
4.仿函数控制大小堆
//比较小于的仿函数，控制大堆 template<class T> struct less { bool operator()(const T& val1,const T& val2) { return val1 < val2; } }; //比较大于的仿函数，控制小堆 template<class T> struct grater { bool operator()(const T& val1, const T& val2) { return val1 > val2; } }; template<class T, class Continer = vector<T>，class Compare =less<T>>//默认大堆 class Priority_queue { public: Compare com; //插入数据 void push(const T& val) { _con.push_back(val); //向上调整 adjust_up(_con.size() - 1); } //删除数据 void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); //向下调整 adjust_down(0); } //返回栈顶数据 const T& top() { return _con[0]; } //判断栈是否为空 bool empty() { return _con.empty(); } private: Continer _con;//适配容器，默认是vector };
五.priority_queue模拟实现整体代码和测试
Queue.hpp:
template<class T, class Continer = vector<T>,class Compare =less<T>> class Priority_queue { public: Compare com; void push(const T& val) { _con.push_back(val); adjust_up(_con.size()-1); } void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } const T& top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: //向上调整算法 void adjust_up(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { if (com(_con[parent] , _con[child])) { swap(_con[parent], _con[child]); 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() && com(_con[child],_con[child + 1])) { child++; } if (com(_con[parent] , _con[child])) { swap(_con[child], _con[parent]); } else { break; } parent = child; child = parent * 2 + 1; } } private: Continer _con; }; }
main:
#include<iostream> #include<vector> #include<list> using std::vector; using std::list; using std::cout; using std::endl; using std::swap; #include"Queue.hpp" using namespace Qikun; int main() { //小堆 Priority_queue<int,std::vector<int>, greater<int>> small_q; //插入数据 small_q.push(2); small_q.push(27); small_q.push(25); small_q.push(244); small_q.push(212); small_q.push(9); //连续取出堆顶数据打印 std::cout << "小堆："; while (!small_q.empty()) { cout << small_q.top()<<' '; small_q.pop(); } cout << endl; //大堆 Priority_queue<int, vector<int>, less<int>> big_q; //插入数据 big_q.push(2); big_q.push(27); big_q.push(25); big_q.push(244); big_q.push(212); big_q.push(9); //连续取出堆顶数据打印 cout << "大堆："; while (!big_q.empty()) { cout << big_q.top() << ' '; big_q.pop(); } return 0; }
编辑
