【C++】STL——priority_queue优先级队列

前言

  上一节我们说了stack和queue这两种容器适配器，而priority_queue（优先级队列）同样也是属于容器适配器，它会优先处理级别较高的值，如数字最大的，其实也就是数据结构中的堆。即物理结构上是数组，逻辑结构上是一颗完全二叉树。

priority_queue的使用

简单使用

库里面的priority_queue：cplusplus–priority_queue

  优先级队列是一种容器适配器，根据某种严格的弱排序标准，使得它的第一个元素总是它所包含的元素中最大的。
  也就类似于堆，其中元素可以随时插入，并且只能检索堆顶元素（优先级队列中位于顶部的元素）。
我们可以先来查看一下priority_queue的类型：
我们使用typeid来查看一个变量的类型。

#include<iostream>
#include<queue>//优先级队列存在于此头文件中
#include<vector>
using namespace std;int main()
{priority_queue<int> pq;cout << typeid(pq).name() << endl;//查看类型return 0;
}

由图，该模板中由两个逗号隔开，代表的意思分别是：

• int：所存储的数据类型
• class std::vector<int,class std::allocator<int> >：底层所使用的容器
• struct std::less<int>：比较方式，默认是less，即小于比较，决定谁的优先级更高。

priority_queue的接口也不多，就以下几个：

函数说明	接口说明
empty()	检测是否为空
size()	返回元素个数
top()	返回优先级队列中最大（最小）元素，即堆顶元素
push(x)	在优先级队列中插入x
pop()	删除优先级队列中最大（最小）元素，即堆顶元素

使用也很简单：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;int main()
{priority_queue<int> pq;//cout << typeid(pq).name() << endl;pq.push(5);pq.push(8);pq.push(3);pq.push(1);pq.push(9);while (!pq.empty())//输出默认大堆，底层按小于号排序{cout << pq.top() << " ";pq.pop();}cout << endl;vector<int> v = { 8,3,6,1,9,4,5 };/*priority_queue<int,vector<int>,greater<int>> pq1;for (auto e : v){pq1.push(e);}*///直接使用迭代器构造priority_queue<int, vector<int>, greater<int>> pq1(v.begin(), v.end());while (!pq1.empty())//输出默认大堆，底层按小于号排序{cout << pq1.top() << " ";pq1.pop();}cout << endl;return 0;
}

结果如下：

  可以看到，一旦我把默认的less比较方式换成了greater< int >，它就能实现小堆。

由于比较方式是在第三个参数，所以如果需要修改，就要把第二个参数一起写上。这就是为什么中间还要写vector< int >的原因。

在OJ中的使用

Leetcode.数组中第k个大的元素
题目如下：
  给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

  题目的意思还是比较容易理解的。我们优先能想到的就是将数组中的值进行排序然后去重，但是任意一种排序方式的时间复杂度都超过了 O(n) ，此时我们就能想到用堆，它既能去重又能排序，则就可以使用优先级队列来解决。
  将所有数放入优先级队列中，默认是大堆，此时不断去除堆顶元素，将前k-1个删掉，再取堆顶元素即可。
代码如下：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq(nums.begin(), nums.end());for(int i = 1; i < k; i++){pq.pop();}return pq.top();}
};

priority_queue的模拟实现

  priority_queue优先级队列，属于容器适配器的一种，它和stack和queue一样，都不需要自己去实现功能，只需要调用底层容器的功能即可，但是为了符合堆的规则，在插入和删除时还是要用到向上调整和向下调整来实现。

  我们先来看一下优先级队列的一个框架，为方便理解，我们先将模板中的第三个参数给去除了：

namespace emm//使用命名空间，防止与库里面的发生冲突
{template<class T, class container = vector<int>>//默认底层容器为vectorclass priority_queue{pubilc:private:container _con;};
}

基本功能

  对于其判空，取大小以及取堆顶元素都可以直接复用底层容器的实现即可。

bool empty() const
{return _con.empty();
}
size_t size() const
{return _con.size();
}
const T& top() const
{return _con.front();
}

  当我想要插入一个元素，我需要先尾插这一个数据，然后根据堆的规则，进行向上调整。

void push(const T& val)
{_con.push_back(val);AdjustUp(size() - 1);
}
void AdjustUp(int child)//大堆
{int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child])//遵循库里面，小于是大堆//如果孩子节点大于父亲节点，则交换{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}

可以通过测试来看看：

运行结果可以看出它是一个大堆。

---

  当我想pop即删除堆顶元素时，就要用到``向下调整法，我们不能直接将堆顶元素删除，那样会破坏堆的规则，所以要先将堆顶元素与最后一个元素进行交换然后将其删除，最后利用向下调整为大堆。
代码如下：

void pop()
{swap(_con[0], _con[_con.size() - 1]);//先交换_con.pop_back();//删除最后一个（堆顶）元素AdjustDown(0);//从堆顶开始向下调整
}
void AdjustDown(int parent)
{int 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[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

这样输出就是排好序的数组了：

---

此时我们将构造函数写上：

//强制生成默认构造
priority_queue() = default;template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)//迭代器区间构造
{while (first != last){push(*first);first++;}
}

仿函数

  当我们按照上面正常写法，想把建大堆改成建小堆时，要把向上调整和向下调整中的小于号都改为大于号，这样操作较为繁琐，那么有没有简单一点的操作呢，答案是有的，也就是仿函数。顾名思义，就是对象可以像函数一样调用。
例如：

当然，括号里面带有参数也是可以的。

此时，我们就可以写出两个比较大小的仿函数：

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

这样就可以使得比较大小可以像函数一样去使用

此时可以将priority_queue中的模板参数变为3个，而参数3的缺省值就是less：

template<class T, class container = vector<int>,class Compare = less<int>>

此时向上调整和向下调整就变为了：

void AdjustUp(int child)//大堆
{Compare com;//实例化一个对象int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])//遵循库里面，小于是大堆//如果孩子节点大于父亲节点，则交换if(com(_con[parent],_con[child]))//对象可以像函数一样直接调用{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}void AdjustDown(int parent)
{Compare com;//实例化一个对象int child = parent * 2 + 1;while (child < _con.size()){/*if (child + 1 < _con.size() && _con[child] < _con[child + 1])*/if (child + 1 < _con.size() && com(_con[child],_con[child+1])){++child;}//if (_con[parent] < _con[child])//遵循库里面，小于是大堆if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

如果我们想要切换成小堆，就按正常操作，写模版实例化时将参数变为greater< int >即可。

vector<int> v = { 8,3,6,1,9,4,5 };
emm::priority_queue<int> pq2(v.begin(), v.end());
while (!pq2.empty())
{cout << pq2.top() << " ";pq2.pop();
}
cout << endl;emm::priority_queue<int, vector<int>, greater<int>> pq3(v.begin(), v.end());
while (!pq3.empty())//变为小堆，按大于号排序
{cout << pq3.top() << " ";pq3.pop();
}
cout << endl;

感谢大家观看，如果大家喜欢，希望大家一键三连支持一下，如有表述不正确，也欢迎大家批评指正。