C++奇迹之旅：快速上手Priority_queue的使用与模拟实现

请添加图片描述

文章目录

  • 📝priority_queue的介绍和使用
  • 🌠 priority_queue的介绍
    • 🌉priority_queue的使用
  • 🌠仿函数的使用
  • 🌠C语言有趣的模仿push_back
  • 🌠priority_queue的模拟实现
  • 🚩总结

📝priority_queue的介绍和使用

🌠 priority_queue的介绍

priority_queue官方文档:https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue
在这里插入图片描述

  1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
  2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中，位于顶部的元素）
  3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从特定容器的尾部弹出，其称为优先队列的顶部。
  4. 底层容器可以是任意标准容器类模版，也可以是其他特定设计的容器类。容器应该可以随机访问迭代器访问，并支持以下的操作：
  • empty()：检测容器是否为空
  • size()：返回容器中有效元素个数
  • front()：返回容器中第一个元素的引用
  • push_back()：在容器尾部插入元素
  • pop_back()：删除容器尾部元素
  1. 标准容器类vector和deque满足这些需求。默认情况下，如果没没有为特定的priority_queue类实例化指定容器类，则使用vector.
  2. 需要支持随机访问迭代器 ，以便始终在内部保持堆结构，容器适配器通过在需要时自动调用算法函数make_heap,push_heap,和pop_heap来完成自动操作

🌉priority_queue的使用

优先级队列默认使用vector作为其底层容器存储数据的容器，在vector上又使用堆算法讲vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的成员位置，都可以考虑使用priority_queue。
注意：默认情况下priority_queue是大堆

数说明接口说明
priority_queue()/priority_queue(first,last)构造空的栈
empty()J检测优先级队列是否为空，是返回true,否则返回false
size()返回元素的个数
top()返回优先级队列中最大(最小元素)，即堆顶元素
push(x)在优先级队列中插入元素
pop()删除优先级队列中最大(最小)元素，即堆顶元素

需要注意的是：

  1. 默认情况下，priority_queue是大堆

在这里插入图片描述

在这里插入图片描述
如果需要要得到小堆，修改比较方式就好，比较方式可以有仿函数，函数指针，函数模板，类模版等等，
比如使用function文件的
在这里插入图片描述
在这里插入图片描述
正常来说，greate是用来降序，大根堆，这里跟往常使用不同，因此，需要注意！！

  1. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。
class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}

	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}

	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}

	friend ostream& operator<<(ostream& _cout, const Date& d);
private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}

struct PDateLess
{
	bool operator()(Date* p1, Date* p2)
	{
		return *p1 < *p2;
	}
};

void TestPriorityQueue()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	bit::priority_queue<Date*, vector<Date*>, PDateLess> q1;
	q1.push(new Date(2018, 10, 29));
	q1.push(new Date(2018, 10, 28));
	q1.push(new Date(2018, 10, 30));

	while (!q1.empty())
	{
		cout << *q1.top() << " ";
		q1.pop();
	}
	cout << endl;
}

int main()
{
	TestPriorityQueue();

	return 0;
}
  1. 如 在OJ中的使用
    数组中的第K个最大元素：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
class Solution {
public:
	int findKthLargest(vector<int>& nums, int k) {
		// 将数组中的元素先放入优先级队列中
		priority_queue<int> p(nums.begin(), nums.end());

		// 将优先级队列中前k-1个元素删除掉
		for (int i = 0; i < k - 1; ++i)
		{
			p.pop();
		}

		return p.top();
	}
};

🌠仿函数的使用

仿函数/函数对象:重载了operator()的类，类的对象可以像函数一样使用operator()特点，参数个数和返回值根据需求确定，不固定，很灵活

// 定义一个仿函数类
class Add {
public:
	// 重载 operator()，接受两个参数并返回它们的和
	int operator()(int a, int b) {
		return a + b;
	}
};

int main() {
	// 创建仿函数对象
	Add add;

	// 使用仿函数
	int result = add(3, 4); // 调用 operator()
	std::cout << "3 + 4 = " << result << std::endl;

	return 0;
}

灵活使用：

class Func
{
public:

	void operator()(int n)
	{
		while (n--)
		{
			cout << "Func调用" << endl;
		}
		cout << endl;
	}
};
int main()
{

	//仿函数
	Func f1;
	f1(10);

	f1.operator()(10);


	return 0;
}

在这里插入图片描述

在这里插入图片描述

🌠C语言有趣的模仿push_back

void PushBack(int x)
{
	printf("void PushBack(int x)\n");
}

// C
struct Vector
{
	void(*push_back)(int);

	int* _a;
	int _size;
	int _capacity;
};

void Init(struct Vector* pv)
{
	pv->push_back = PushBack;
	//...
}

int main()
{
	Vector v;
	Init(&v);

	v.push_back(1);
	v.push_back(2);

	return 0;
}

在这里插入图片描述

🌠priority_queue的模拟实现

通过对priority_queue的底层结构就是堆，因此此处只需对对进行通用的封装即可。

  1. 基本框架
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

namespace own
{
	template<class T>
	struct myless
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

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

	template <class T,class Container = vector<T>,class Compare = myless<T>>
	class priority_queue
	{
	public:
		//强制编译器生成
		priority_queue() = default;

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

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

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}
  1. 使用迭代器添加元素数据进数组：
    当数据都进vector容器，我们随带建堆：
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		_con.push_back(*first);
		++first;
	}

	//从顶开始建堆
	for (size_t i = 0 ;i < _con.size();++i)
	{
		adjustup(i);
	}
}
  1. 建堆两种方式：向上建堆：向下建堆：
    在这里插入图片描述
//第一种
void adjustup(size_t child)
{
	Compare comfunc;
	while (child > 0)
	{
		size_t parent = (child - 1) / 2;
		if (comfunc(_con[parent], _con[child]))
		{
			swap(_con[parent], _con[child]);
			child = parent;
			parent = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//第二种
void adjustup(int child)
{
	Compare comfunc;

	while (child > 0)
	{
		size_t parent = (child - 1) / 2;
		if (comfunc(_con[parent], _con[child]))
		{
			swap(_con[child], _con[parent]);

			child = parent;

			//加不加这个parent都可以，因为上面可以再次获取,加了可以方便理解
			//parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
//}

//第三种
 //也可以是这样的写法
void adjustup(int child)
{
	Compare comfunc;
	size_t parent = (child - 1) / 2;
	//                      
	// 注意：这里的parent 和child的顺序要和adjustdown的if (comfunc(_con[parent] , _con[child]))比较顺序一致
	while (comfunc(_con[parent] , _con[child])) {
		swap(_con[child], _con[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
}
  1. 向下调整建堆：
void adjustdown(int parent)
{
	Compare comfunc;
	size_t child = 2 * parent + 1;

	while (child < _con.size())
	{
		if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1]))
		{
			++child;
		}

		if (comfunc(_con[parent] , _con[child]))//注意：这里的parent 和child的顺序要和adjustupwhile (comfunc(_con[parent] , _con[child]))顺序一致
		{
			swap(_con[parent], _con[child]);

			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
  1. 两个操作push和pop
    在这里插入图片描述
void push(const T& x)
{
	_con.push_back(x);
	adjustup(_con.size() - 1);
}

void pop()
{
	std::swap(_con[0], _con[_con.size()-1]);
	_con.pop_back();

	adjustdown(0);
}

在这里插入图片描述

priority_queue的源代码：

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

namespace own
{
	template<class T>
	struct myless
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

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

	template <class T,class Container = vector<T>,class Compare = myless<T>>
	class priority_queue
	{
	public:
		//强制编译器生成
		priority_queue() = default;

		//
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			//从顶开始建堆
			for (size_t i = 0 ;i < _con.size();++i)
			{
				adjustup(i);
			}
		}


		//void adjustup(size_t child)
		//{
		//	Compare comfunc;
		//	while (child > 0)
		//	{
		//		size_t parent = (child - 1) / 2;
		//		if (comfunc(_con[parent], _con[child]))
		//		{
		//			swap(_con[parent], _con[child]);
		//			child = parent;
		//			parent = child * 2 + 1;
		//		}
		//		else
		//		{
		//			break;
		//		}
		//	}
		//}

		//void adjustup(int child)
		//{
		//	Compare comfunc;

		//	while (child > 0)
		//	{
		//		size_t parent = (child - 1) / 2;
		//		if (comfunc(_con[parent], _con[child]))
		//		{
		//			swap(_con[child], _con[parent]);

		//			child = parent;

		//			//加不加这个parent都可以，因为上面可以再次获取,加了可以方便理解
		//			//parent = (child - 1) / 2;
		//		}
		//		else
		//		{
		//			break;
		//		}
		//	}
		//}

		//i 为child
		 //也可以是这样的写法
		void adjustup(int child)
		{
			Compare comfunc;
			size_t parent = (child - 1) / 2;
			//                      
			// 注意：这里的parent 和child的顺序要和adjustdown的if (comfunc(_con[parent] , _con[child]))比较顺序一致
			while (comfunc(_con[parent] , _con[child])) {
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
		}
		
		//i为parent
		void adjustdown(int parent)
		{
			Compare comfunc;
			size_t child = 2 * parent + 1;

			while (child < _con.size())
			{
				if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1]))
				{
					++child;
				}

				if (comfunc(_con[parent] , _con[child]))//注意：这里的parent 和child的顺序要和adjustupwhile (comfunc(_con[parent] , _con[child]))顺序一致
				{
					swap(_con[parent], _con[child]);

					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}




		void push(const T& x)
		{
			_con.push_back(x);
			adjustup(_con.size() - 1);
		}

		void pop()
		{
			std::swap(_con[0], _con[_con.size()-1]);
			_con.pop_back();

			adjustdown(0);
		}

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

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

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

🚩总结

请添加图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/875229.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

java重点学习-集合（List）

java重点学习-集合（List）

七 集合&#xff08;List&#xff09; 7.1 复杂度分析 7.2 数组 1.数组(Array)是一种用连续的内存空间存储相同数据类型 数据的线性数据结构。 2.数组下标为什么从0开始 寻址公式是:baseAddressi*dataTypeSize&#xff0c;计算下标的内存地址效率较高 3.查找的时间复杂度 随机(…
阅读更多...
HarmonyOS Next系列之实现一个左右露出中间大两边小带缩放动画的轮播图（十二）

HarmonyOS Next系列之实现一个左右露出中间大两边小带缩放动画的轮播图（十二）

系列文章目录 HarmonyOS Next 系列之省市区弹窗选择器实现&#xff08;一&#xff09; HarmonyOS Next 系列之验证码输入组件实现&#xff08;二&#xff09; HarmonyOS Next 系列之底部标签栏TabBar实现&#xff08;三&#xff09; HarmonyOS Next 系列之HTTP请求封装和Token…
阅读更多...
一种多策略改进小龙虾智能优化算法MSCOA 改进策略：种群混沌映射初始化+透镜成像反向学习+黄金正弦变异策略

一种多策略改进小龙虾智能优化算法MSCOA 改进策略：种群混沌映射初始化+透镜成像反向学习+黄金正弦变异策略

一种多策略改进小龙虾智能优化算法MSCOA 改进策略&#xff1a;种群初始化精英反向透镜成像反向学习黄金正弦变异策略 文章目录 一、小龙虾COA基本原理二、改进策略2.1种群初始化 映射2.2 透镜成像反向学习2.3 黄金正弦变异策略 三、实验结果四、核心代码五、代码获取六、总结 一…
阅读更多...
小型企业如何利用人工智能的生产力

小型企业如何利用人工智能的生产力

尽管生产力低下是一个长期存在的问题&#xff0c;但最近严峻的经济逆风加剧了这一问题&#xff0c;企业清算数量同比增长了 19&#xff05;。 Xero 的报告《小企业生产力&#xff1a;趋势、影响和战略》反映了这些宏观经济变化&#xff0c;显示 2023 年新西兰小企业生产力与 …
阅读更多...
SiC,GaN驱动优选驱动方案SiLM5350系列SiLM5350MDDCM-DG 带米勒钳位Clamp保护功能 单通道隔离栅极驱动器

SiC,GaN驱动优选驱动方案SiLM5350系列SiLM5350MDDCM-DG 带米勒钳位Clamp保护功能 单通道隔离栅极驱动器

SiLM5350MDDCM-DG是一款适用于IGBT、MOSFET的单通道 隔离门极驱动器&#xff0c;具有10A拉电流和10A灌电流驱动能 力。提供内部钳位功能&#xff0c;可单独控制 上升时间和下降时间。 在 SOP8 封 装 中 具 有 3000VRMS 隔 离 耐 压 &#xff08; 符 合 UL1577&#xff09;。 与…
阅读更多...
抖音微信超火国庆节国旗头像生成源码

抖音微信超火国庆节国旗头像生成源码

源码介绍&#xff1a; 抖音微信超火国庆节国旗头像生成源码&#xff0c;静态页前端生成速度超快&#xff01;源码直接上传到服务器即可使用。 1、打开地址后点击上传->选一张你喜欢的头像->然后点右边箭头符合选款式->最后点保存头像->按照提示 2、保存到手机即…
阅读更多...
c/c++面试100道

c/c++面试100道

1.一道笔试题解析_哔哩哔哩_bilibili P20&#xff1a;#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE*)0)->MEMBER) 1、 offsetof 宏是 C 语言中用于计算结构体成员相对于结构体起始地址的偏移量的宏定义。这个宏的定义如下&#xff1a; #define offsetof(TYPE, …
阅读更多...
macOS上谷歌浏览器的十大隐藏功能

macOS上谷歌浏览器的十大隐藏功能

谷歌浏览器&#xff08;Google Chrome&#xff09;在macOS上拥有一系列强大而隐蔽的特性&#xff0c;这些功能能显著提高您的浏览体验。从多设备同步到提升安全性和效率&#xff0c;这些被低估的功能等待着被发掘。我们将逐步探索这些功能&#xff0c;帮助您最大化利用谷歌浏览…
阅读更多...
09-排序1 排序（C）

09-排序1 排序（C）

这一节&#xff0c;测试各类排序算法的运行速度&#xff08;没有基数排序&#xff08;桶&#xff09; 其实在实际学习中&#xff0c;还是有意义的 给定 n 个&#xff08;长整型范围内的&#xff09;整数&#xff0c;要求输出从小到大排序后的结果。 本题旨在测试各种不同的排序…
阅读更多...
【代码随想录训练营第42期 Day57打卡 - 图论Part7 - Prim算法

【代码随想录训练营第42期 Day57打卡 - 图论Part7 - Prim算法

一、Prim算法 Prim算法是一种贪心算法&#xff0c;用于求解加权无向图的最小生成树问题。其中&#xff0c;最小生成树是指一个边的子集&#xff0c;它连接图中的所有顶点&#xff0c;且边的总权重最小&#xff0c;并且没有形成环。 对于Prim算法的简单了解&#xff0c;这里推…
阅读更多...
基于小程序的教学辅助微信小程序设计+ssm（lw+演示+源码+运行）

基于小程序的教学辅助微信小程序设计+ssm（lw+演示+源码+运行）

教学辅助微信小程序 摘 要 随着移动应用技术的发展&#xff0c;越来越多的学生借助于移动手机、电脑完成生活中的事务&#xff0c;许多的传统行业也更加重视与互联网的结合&#xff0c;由于学生学习的压力越来越大&#xff0c;教学辅助是一个非常不错的教育平台&#xff0c;对…
阅读更多...
9.12-kubeadm方式安装k8s+基础命令的使用

9.12-kubeadm方式安装k8s+基础命令的使用

一、安装环境 编号主机名称ip地址1k8s-master192.168.2.662k8s-node01192.168.2.773k8s-node02192.168.2.88 二、前期准备 1.设置免密登录 [rootk8s-master ~]# ssh-keygen[rootk8s-master ~]# ssh-copy-id root192.168.2.77[rootk8s-master ~]# ssh-copy-id root192.168.2.…
阅读更多...
指令——计算机的语言(part 2)

指令——计算机的语言(part 2)

目录 1.1 翻译并执行程序 1.1.1 编译器 1.1.2 汇编器 1.1.3 链接器 1.1.4 加载器 1.1.5 动态链接库 接上一篇文章: 指令——计算机的语言(part 1) 1.1 翻译并执行程序 程序翻译层次图如下: 首先高级语言比如说C&#xff0c;会被编译器编译成汇编语言&#xff0c;然后汇…
阅读更多...
Python面试宝典第48题：找丑数

Python面试宝典第48题：找丑数

题目 我们把只包含质因子2、3和5的数称作丑数&#xff08;Ugly Number&#xff09;。比如&#xff1a;6、8都是丑数&#xff0c;但14不是&#xff0c;因为它包含质因子7。习惯上&#xff0c;我们把1当做是第一个丑数。求按从小到大的顺序的第n个丑数。 示例 1&#xff1a; 输入…
阅读更多...
另类动态规划

另类动态规划

前言&#xff1a;一开始我根本想不到这个题目是一个动态规划的题目&#xff0c;而且我一开始的初始状态还写错了 我还忘记了写算法题的基本步骤&#xff0c;先看数据范围&#xff0c;再考虑能不能用动态规划写 题目地址 #include <bits/stdc.h> using namespace std; #de…
阅读更多...
3C电子胶黏剂在手机制造方面有哪些关键的应用

3C电子胶黏剂在手机制造方面有哪些关键的应用

3C电子胶黏剂在手机制造方面有哪些关键的应用 3C电子胶黏剂在手机制造中扮演着至关重要的角色&#xff0c;其应用广泛且细致&#xff0c;覆盖了手机内部组件的多个层面&#xff0c;确保了设备的可靠性和性能。以下是电子胶在手机制造中的关键应用&#xff1a; 手机主板用胶&…
阅读更多...
浏览器百科：网页存储篇-IndexedDB介绍（十）

浏览器百科：网页存储篇-IndexedDB介绍（十）

1.引言 在现代网页开发中&#xff0c;数据存储需求日益增多和复杂&#xff0c;传统的客户端存储技术如localStorage和sessionStorage已难以满足大型数据的存储和管理需求。为了解决这一问题&#xff0c;HTML5 引入了 IndexedDB&#xff0c;在本篇《浏览器百科&#xff1a;网页…
阅读更多...
网络学习-eNSP配置路由器

网络学习-eNSP配置路由器

#PC1网关&#xff1a;192.168.1.254 #PC3网关&#xff1a;192.168.3.254 #PC4网关&#xff1a;192.168.4.254# 注&#xff1a;路由器接口必须配置不同网段IP地址 <Huawei>system-view Enter system view, return user view with CtrlZ. #给路由器两个接口配置IP地址 [Hua…
阅读更多...
IBM中国研发中心撤出：挑战与机遇并存

IBM中国研发中心撤出：挑战与机遇并存

IBM中国研发中心撤出&#xff1a;挑战与机遇并存 引言 近日&#xff0c;IBM宣布撤出在中国的两大研发中心的消息&#xff0c;引起了广泛关注。这一举动不仅对IBM自身的全球布局产生了影响&#xff0c;也在一定程度上反映了跨国公司在中国市场策略的调整。本文将探讨这一事件背…
阅读更多...
keras和tensorflow可用的一组版本

keras和tensorflow可用的一组版本

目录 keras版本&#xff1a;3.5.0tensorflow&#xff1a;2.17.0之前的错误导包现在的正确导包 keras版本&#xff1a;3.5.0 tensorflow&#xff1a;2.17.0 之前的错误导包 其实也不是说错误&#xff0c;就是因为文件位置不对&#xff0c;所以VSCode总是有黄色波浪线&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023