目录
- 前言
- priority_queue的使用
- 简单使用
- 在OJ中的使用
- 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>>
//默认底层容器为vector
class 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;
}
else
break;
}
}
可以通过测试来看看:
运行结果可以看出它是一个大堆。
当我想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;
}
else
break;
}
}
这样输出就是排好序的数组了:
此时我们将构造函数写上:
//强制生成默认构造
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;
}
else
break;
}
}
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;
}
else
break;
}
}
如果我们想要切换成小堆,就按正常操作,写模版实例化时将参数变为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;
感谢大家观看,如果大家喜欢,希望大家一键三连支持一下,如有表述不正确,也欢迎大家批评指正。