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

目录

• 前言
• 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;

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