C++ STL priority_queue

目录

一.认识priority_queue

二. priority_queue的使用

三.仿函数

 1.什么是仿函数

 2.控制大小堆

 3.TopK问题

四.模拟实现priority_queue

 1.priority_queue的主要接口框架

 2.堆的向上调整算法

 3.堆的向下调整算法

 4.仿函数控制大小堆

 五.priority_queue模拟实现整体代码和测试

---

一.认识priority_queue

priority_queue----reference

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;
}