在这里插入图片描述

文章目录

一、priority_queue是什么以及它的使用

priority_queue也就是优先级队列，它的本质上是一个堆，没错，就是我们在之前初阶数据结构学习的那个堆，如果还有小伙伴不知道什么是堆，推荐看以下文章：【初阶数据结构和算法】二叉树顺序结构—堆的定义与实现(附源码)

接下来我们来看看它有哪些接口，我们简单学习一下，用这些接口实现一个堆排，如下：
在这里插入图片描述
里面很多接口我们都非常熟悉了，再结合堆的特点，我们不难猜到它们的作用，接下来我们就简单使用一下这些接口来实现应该仿堆排，如下：

#include <iostream>
//priority_queue也被包含在了queue这个头文件中
#include <queue>
#include <vector>

int main()
{
	//创建一个待排序数组
	std::vector<int> v = { 235, 432, 212,1,3,26,4, 21 };
	//将数组中的元素给priority_queue, 默认是一个大堆
	std::priority_queue<int> pq(v.begin(), v.end());
	std::cout << "size: " << pq.size() << std::endl;
	//这里一直取栈顶元素，然后pop栈顶元素，最后是一个降序
	//因为默认是一个大堆，栈顶元素总是当前堆最大的
	while (!pq.empty())
	{
		std::cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

按照预期我们应该将数组排成了降序，我们来看看代码运行结果，如下：
在这里插入图片描述
可以看到确实是这样，那我们又如何排成升序呢？关键在于如何把这个大堆改成小堆，这里采用的方法就是传一个仿函数，但是比较坑的地方是什么呢？这里传仿函数是反着传的
在我们一般的想法中，传less肯定就是小堆，因为小的优先级高，传greater就是大堆，也就是和sort进行对应的，但是恰恰相反，priority_queue中，传greater是小堆，传less是大堆，这也是比较坑的一点，需要我们注意
priority_queue使用模板参数来传递仿函数，但是在传递仿函数之前要传递它的底层容器，没错，priority_queue也是一个容器适配器，一般使用vector进行适配，所以如果我们要把上面的例子改成小堆应该这样操作：

#include <iostream>
//priority_queue也被包含在了queue这个头文件中
#include <queue>
#include <vector>

int main()
{
	//创建一个待排序数组
	std::vector<int> v = { 235, 432, 212,1,3,26,4, 21 };
	//将数组中的元素给priority_queue, 默认是一个大堆
	//std::priority_queue<int> pq(v.begin(), v.end());
	std::priority_queue<int, std::vector<int>, std::greater<int>> pq(v.begin(), v.end());
	std::cout << "size: " << pq.size() << std::endl;
	//这里一直取栈顶元素，然后pop栈顶元素，最后是一个降序
	//因为默认是一个大堆，栈顶元素总是当前堆最大的
	while (!pq.empty())
	{
		std::cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

我们来看看代码运行结果，如下：
在这里插入图片描述
可以看到现在排出来是升序，说明我们的堆此时是一个小堆，那么关于优先级队列的介绍和使用就到这里，接下来我们来实现一下priority_queue

二、priority_queue的初步实现

我们首先来初步实现一下priority_queue，这个初版不能通过仿函数来控制大小堆，只能默认一种建堆方式，我们在后面添加上对仿函数的处理
首先我们要认识到priority_queue的底层其实也是一个动态扩容的数组，只是这个数组需要保证堆的规则，所以我们还是可以使用vector作为它的底层容器，这样我们写起来就简单很多了
主要是要会向上调整和向下调整算法，如果不会的可以看本篇文章开头推荐的那篇博客，里面详细写了如何实现向上调整和向下调整，接下来我们开始来着手实现

priority_queue的基本结构

它的基本结构和之前写的queue以及stack很相似，因为它们都是容器适配器，如下：

#include <iostream>
#include <vector>

namespace TL
{
	//暂时不添加仿函数，先大致跑通后面补充，这里先按默认大堆写
	template<class T, class Container = std::vector<T>>
	class priority_queue
	{
	public:
		
	private:
		Container _con;
	};
}

empty、size和top

empty和size我们直接复用底层容器的empty和size即可，top是返回堆顶元素，也就是容器中下标为0的元素，如下：

bool empty()
{
	return _con.empty();
}

size_t size() const
{
	return _con.size();
}

T& top()
{
	return _con[0];
}

const T& top() const
{
	return _con[0];
}

push

push就比较复杂了，它虽然可以复用底层容器的尾插接口，但是我们要注意这是一个堆，所以我们在尾插后，需要进行向上调整算法，这里我们直接给出向上调整算法以及push，如下：

void AdjustUp(int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//我们要建大堆，所以和父亲比谁大
		if (_con[child] > _con[parent])
		{
			Swap(_con[child], _con[parent]);
		}
		else
		{
			child = parent;
			parent = (child - 1) / 2;
		}
	}
}

void push(const T& x)
{
	_con.push_back(x);
	//插入一个元素后向上调整
	AdjustUp(size() - 1);
}

pop

堆删除的都是堆顶元素，也就是下标为0的元素，但是如果直接删除下标为0的元素，会导致整个堆的结构都受到破坏，所以我们采用的方法就是先把头尾元素进行交换，然后尾删就好了，然后对0下标位置的元素进行向下调整，如下：

void AdjustDown(int parent)
{
	//现在是左孩子，等下需要比较左右孩子大小
	//由于我们要建大堆，所以父亲和大孩子比谁大
	int child = parent * 2 + 1;
	while (child < size())
	{
		if (child + 1 < size() && _con[child + 1] > _con[child])
		{
			child++;
		}
		if (_con[child] > _con[parent])
		{
			Swap(_con[child], _con[parent]);
		}
		else
		{
			parent = child;
			child = 2 * parent + 1;
		}
	}

}

默认成员函数

之前的stack和queue有自己严格的插入和删除规则，所以没有实现大括号初始化，或者按照一个迭代器区间进行初始化， 但是我们的优先级队列是支持的，所以我们简单实现两个构造
一个构造支持大括号初始化(std::priority_queue没有)，一个构造支持拷贝一段迭代器区间初始化，有两种方式，一种就是直接遍历容器，用push把元素插入到堆中，这样的话时间复杂度为O(n * logn)
还有一种方法就是先把全部元素插入到底层容器，不管堆的规则，然后再使用向下调整建堆算法建堆，全部插入到底层容器的复杂度为O(n)，向下调整建堆的复杂度为O(n)，所以总体上时间复杂度为O(n)，要优于直接插入
这里我们两个方法都写一写，如下：

//支持迭代器区间构造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
	/*InputIterator it = first;
	while (it != last)
	{
		push(*it);
		it++;
	}*/
	InputIterator it = first;
	while (it != last)
	{
		_con.push_back(*it);
		it++;
	}
	//向下调整建堆O(n)，更快
	for (int i = (size() - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(i);
	}
	//向上调整建堆O(n * logn)
	/*for (int i = 0; i < size(); i++)
	{
		AdjustUp(i);
	}*/

}

//支持大括号初始化
priority_queue(const std::initializer_list<T>& il)
{
	/*for (auto& e : il)
	{
		push(e);
	}*/
	for (auto& e : il)
	{
		_con.push_back(e);
	}
	//向下调整建堆O(n)，更快
	for (int i = (size() - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(i);
	}
	//向上调整建堆O(n * logn)
	/*for (int i = 0; i < size(); i++)
	{
		AdjustUp(i);
	}*/
}

测试

我们就拿之前的代码作测试，如下：

#include <queue>
#include "priority_queue.h"

int main()
{
	//创建一个待排序数组
	std::vector<int> v = { 235, 432, 212,1,3,26,4, 21 };
	//将数组中的元素给priority_queue, 默认是一个大堆
	TL::priority_queue<int> pq(v.begin(), v.end());
	std::cout << "size: " << pq.size() << std::endl;
	//这里一直取栈顶元素，然后pop栈顶元素，最后是一个降序
	//因为默认是一个大堆，栈顶元素总是当前堆最大的
	while (!pq.empty())
	{
		std::cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

我们来看看代码运行结果，如下：
在这里插入图片描述
可以看到没有问题，默认是大堆，接下来我们开始为我们的priority_queue添加仿函数，使用户可以自行控制比大小的规则

三、添加仿函数，更加灵活

首先第一步，我们要给我们的模板添加一个仿函数(一个类类型)，由于默认是大堆，所以我们默认给less，如下：

template<class T, class Container = std::vector<T>, class Compare = std::less<T>>

要注意的是，模板参数传过来的是一个类型，所以我们要用这个类型创建一个仿函数对象，然后用这个对象去支持比较，而比较的地方只有向上调整和向下调整，还是比较好修改的，如下：

void AdjustUp(int child)
{
	Compare compare;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//我们要建大堆，所以和父亲比谁大
		//注意和之前不一样，less是大堆，所以比较的地方要取反
		if (!compare(_con[child], _con[parent]))
		{
			Swap(_con[child], _con[parent]);
		}
		else
		{
			child = parent;
			parent = (child - 1) / 2;
		}
	}
}

void AdjustDown(int parent)
{
	Compare compare;
	//现在是左孩子，等下需要比较左右孩子大小
	//由于我们要建大堆，所以父亲和大孩子比谁大
	int child = parent * 2 + 1;
	while (child < size())
	{
		//注意和之前不一样，less是大堆，所以比较的地方要取反
		if (child + 1 < size() && !compare(_con[child + 1], _con[child]))
		{
			child++;
		}
		if (!compare(_con[child], _con[parent]))
		{
			Swap(_con[child], _con[parent]);
		}
		else
		{
			parent = child;
			child = 2 * parent + 1;
		}
	}

那么到这里我们的priority_queue就差不多实现好了，接下来我们来测试一下：

#include <iostream>
#include "priority_queue.h"

int main()
{
	//使用大括号初始化一个小堆(std::priority_queue没有)，排升序
	TL::priority_queue<int, std::vector<int>, std::greater<int>> pq = { 235, 432, 212,1,3,26,4, 21 };
	std::cout << "size: " << pq.size() << std::endl;
	while (!pq.empty())
	{
		std::cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

我们来看看代码运行结果：
在这里插入图片描述

可以看到没有问题，那么今天关于仿函数和priority_queue的实现就讲到这里，有什么不懂欢迎私信问我，我会及时做出解答，下一篇文章开始我们学习模板进阶了，敬请期待吧！
bye~

# c++ # 开发语言 # 算法 # 数据结构 # 经验分享
Logo
亚马逊云科技技术品牌专区

更多推荐

测试流量、测试粉丝

💎【行业认证·权威头衔】✔ 华为云天团核心成员：特约编辑/云享专家/开发者专家/产品云测专家✔ 开发者社区全满贯：CSDN博客&商业化双料专家/阿里云签约作者/腾讯云内容共创官/掘金&亚马逊&51CTO顶级博主✔ 技术生态共建先锋：横跨鸿蒙、云计算、AI等前沿领域的技术布道者🏆【荣誉殿堂】🎖 连续三年蝉联"华为云十佳博主"（2022-2024）🎖 双冠加冕CSDN"年度博客之星TOP2"（

avatar 亚马逊云科技技术品牌专区

人工智能训练的核心秘密：梯度下降与L1/L2正则化

y_true = 2预测值 10 比真实值 2 大了 8，模型错了。定义一个函数，用来量化"错得有多严重"。这个函数叫损失函数，我们用均方误差把当w = 10这个 64 代表当前模型的错误程度。方法解决的问题梯度公式对参数的作用梯度下降如何找到让损失最小的参数梯度 = 2×误差×x_k让每个参数朝损失减小的方向移动L2 正则化防止参数过大导致过拟合梯度 = 2×误差×x_k + 2×λ×w_k所有

avatar 亚马逊云科技技术品牌专区

ESP32-S3硬件加密性能实测

对于ESP32-S3物联网设备，

avatar 亚马逊云科技技术品牌专区