【C++】学习笔记——优先级队列

文章目录

  • 十、优先级队列
    • 1. priority_queue的介绍
    • 2. 优先级队列如何使小的数据优先级高
    • 3. 仿函数介绍
    • 4. priority_queue的模拟实现
  • 补： 反向迭代器
  • 未完待续

十、优先级队列

1. priority_queue的介绍

优先级队列 其实也不属于队列，它跟 stack 和 queue 一样，都是 容器适配器 。
在这里插入图片描述
优先级队列的默认适配容器是 vector 。要使用优先级队列的话，需要包含 queue 头文件 。
在这里插入图片描述
优先级队列的接口也非常简单明了，我们来简单试一下：

#include<iostream>
// 包含 queue 头文件
#include<queue>
using namespace std;

int main()
{
	priority_queue<int> pq;
	pq.push(3);
	pq.push(1);
	pq.push(4);
	pq.push(2);

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

	return 0;
}

在这里插入图片描述
我们插入的数据是 3 1 4 2 ，打印出来的数据却是 4 3 2 1 ，竟然将其排了个降序，这有点像我们之前学过的一种数据结构啊。是的，它很像 堆，它底层其实就是 大根堆 。优先级队列 就是按优先级取数据，堆顶数据就是优先级最高的。

2. 优先级队列如何使小的数据优先级高

优先级队列默认是大根堆，大的数据优先级高，那么我们该如何使小的数据优先级高呢？就是使优先级队列以 小根堆 的形式实现。答案嘛，就涉及到 STL 的另一个组件了—— 仿函数 。
在这里插入图片描述
优先级队列 模板的第三个参数就是仿函数，默认是 less （小于），如果要使其成 小根堆 的形式，则需要将其参数修改为 greater （大于），由于缺省参数不能跳跃着传，所以需要将前面两个参数都给加上才行。

// 三个参数
priority_queue<int, vector<int>, greater<int>> pq;

我们来使用一下：

#include<iostream>
#include<queue>
using namespace std;

int main()
{
	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(3);
	pq.push(1);
	pq.push(4);
	pq.push(2);

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

	return 0;
}

在这里插入图片描述
在其他有这种仿函数的函数中，less 默认都是排升序 ，greater 都是排降序 ，比如 sort 函数 ，而 优先级队列 中，less 是大根堆 ， greater 是小根堆 。

// sort 排降序
sort(v.begin(), v.end(), greater<int>());

注意，sort 函数 的第三个参数是函数参数，需要传对象，所以末尾带着 () 来创建匿名对象，而 优先级队列 则是类模板，传类型，不需要带 () 。

3. 仿函数介绍

仿函数其实是一个类型 ，一种结构。

struct Less
{
	// 重载 ()
	bool operator()(const int& x, const int& y)
	{
		return x < y;
	}
};

我们要怎样使用这个类呢？

int main()
{
	Less Lessfunc;

	cout << Lessfunc(1, 2) << endl;
	// 上面写法本质上是下面写法
	cout << Lessfunc.operator()(1, 2) << endl;

	return 0;
}

在这里插入图片描述
大家有没有发现，上面的写法 很像函数 啊，Lessfunc 就像函数名一样，但是没想到其实他是对象名。所以 仿函数就是对象很像函数的类型 。把模板套上就可以使类型泛型。

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

所以在 sort 函数 里的第三个参数，greate< int >() 就是一个匿名对象，类型是 int ，调用重载 () 符号。

4. priority_queue的模拟实现

先把简单的框架搭好，再来挨个实现。由于 STL库 里的 priority_queue 是位于 queue 头文件里，所以我们这里头文件取名为 Queue.h 。

// Queue.h
#pragma once

namespace my
{
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		void push(const T& x)
		{

		}

		void pop()
		{

		}

		bool empty()
		{

		}

		size_t size()
		{

		}

		const T& top()
		{

		}
	private:
		Container _con;
	};
}

我们来想一想，我们的堆是如何插入数据的：堆是尾部插入数据，然后向上调整位置 。那堆是如何删除数据的呢？堆是收尾交换数据，然后尾删，最后将堆顶数据向下调整 。

#pragma once

namespace my
{
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:

		adjust_up(size_t child)
		{

		}

		adjust_down(size_t parent)
		{

		}

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

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

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

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

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

向上调整函数注意的就是什么情况可以向上调整，当孩子的值比父亲大时，需要将孩子的位置与父亲的位置进行交换 ，然后更新孩子和父亲的下标。那什么时候结束调整呢？当孩子的值比不父亲的值大，或者孩子已经到堆顶位置 此时需要结束调整。

adjust_up(size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_con[child] > _con[parent])
		{
			// 交换数据
			std::swap(_con[child], _con[parent]);
			// 更新下标
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{ 
			break;
		}
	}
}

向下调整需要注意的是，父节点要是最大的值，所以要交换也是与最大的孩子交换，第一步需要找到最大的孩子 ，然后 判断父亲是否比孩子小，小则交换，最后判断结束条件 父节点已经不再比最大的孩子小或者，已经到达叶子节点 则退出。

adjust_down(size_t parent)
{
	size_t child = parent * 2 + 1;
	// 左孩子孩子存在
	while (child < _con.size())
	{
		// 右孩子存在且比左孩子大
		if (child + 1 < _con.size() && _con[child + 1] > _con[child])
		{
			++child;
		}

		if (_con[parent] < _con[child])
		{
			// 交换
			std::swap(_con[parent], _con[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

除了仿函数外，我们的代码已经实现到了：

// Queue.h
#pragma once
#include<vector>
namespace my
{
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:

		void adjust_up(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_con[child] > _con[parent])
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{ 
					break;
				}
			}
		}

		void adjust_down(size_t parent)
		{
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				{
					++child;
				}

				if (_con[parent] < _con[child])
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

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

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

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

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

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

// test.cpp
#include<iostream>
#include"Queue.h"
using namespace std;

int main()
{
	my::priority_queue<int> pq;
	pq.push(1);
	pq.push(3);
	pq.push(4);
	pq.push(2);

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

	return 0;
}

在这里插入图片描述
OK，这里默认大堆就已经完成了。但是我们这个代码并不能控制变成小堆，我们需要 使用仿函数来控制比较逻辑 。

// 在 my 命名空间内
template<class T>
class less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

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

有了仿函数，所以我们的优先级队列模板参数就要将其加上。

// 默认大根堆，第三个参数默认是仿函数 less
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
	//
private:
	//
};

所以，类里的比较大小的判断就可以使用仿函数来调用对象来实现。

void adjust_up(size_t child)
{
	// 这里
	Compare com;
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		// _con[parent] < _con[chlid]
		if (com(_con[parent], _con[child]))
		{
			std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{ 
			break;
		}
	}
}

void adjust_down(size_t parent)
{
	// 这里
	Compare com;
	size_t child = parent * 2 + 1;
	while (child < _con.size())
	{
		// _con[child] < _con[child + 1]
		if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
		{
			++child;
		}

		//_con[parent] < _con[child]
		if (com(_con[parent], _con[child]))
		{
			std::swap(_con[parent], _con[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

测试一下：

#include<iostream>
#include"Queue.h"
using namespace std;

int main()
{
	// 大堆
	my::priority_queue<int> pq;
	pq.push(1);
	pq.push(3);
	pq.push(4);
	pq.push(2);

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

	// 小堆
	my::priority_queue<int, vector<int>, greater<int>> pq2;
	pq2.push(1);
	pq2.push(3);
	pq2.push(4);
	pq2.push(2);

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

	return 0;
}

在这里插入图片描述

可以。

补： 反向迭代器

反向迭代器其实可以通过修改正向迭代器来达到目的，但是我们要求代码复用，所以需要用另一种方法来实现反向迭代器。此时我们可以使用 迭代器适配器 来实现所有容器的反向迭代器。你给我一个容器的正向迭代器，我来帮你实现其反向迭代器。

反向迭代器和正向迭代器的不同点在哪？功能类似，++和–方向不一样 。
其中反向迭代器的模板部分代码就如下所示，只需要注意反向迭代器要正确调用正向迭代器的函数就能成功实现。比如：++调用–，–调用++。

#pragma once
namespace me
{
	template<class Iterator, class Ref, class Ptr>
	class ReverseIterator
	{
	public:
		typedef ReverseIterator<Iterator, Ref, Ptr> Self;

		Iterator _it;
		
		ReverseIterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()
		{
			Iterator tmp = _it;
			return *(--tmp);
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		// 前置++
		Self& operator++()
		{
			--_it;
			return *this;
		}

		// 前置--
		Self& operator--()
		{
			++_it;
			return *this;
		}

		bool operator!=(const Self& s)
		{
			return _it != s._it;
		}
	};
}

未完待续

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

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

相关文章

【MQTT】mosquitto 的 “下载、交叉编译、使用” 详细教程，手把手搭建一个MQTT Broker

【MQTT】mosquitto 的 “下载、交叉编译、使用” 详细教程，手把手搭建一个MQTT Broker

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…
阅读更多...
ARIMA模型在河流水质预测中的应用_含代码

ARIMA模型在河流水质预测中的应用_含代码

#水质模型 #时间序列 #python应用 ARIMA 时间序列模型简介 时间序列是研究数据随时间变化而变化的一种算法&#xff0c;是一种预测性分析算法。它的基本出发点就是事物发展都有连续性&#xff0c;按照它本身固有的规律进行。ARIMA(p,d,q)模型全称为差分自回归移动平均模型 (A…
阅读更多...
macbookpro 安装linux mint 无线wifi无法连接 解决方案

macbookpro 安装linux mint 无线wifi无法连接 解决方案

见欢迎页面—驱动管理
阅读更多...
单链表经典oj题(2)

单链表经典oj题(2)

前言 这次将要把剩下的oj题将以图解和自己的理解把它讲解完&#xff0c;希望对大家有所帮助&#xff0c;这次的讲解也是干货 第一题 21. 合并两个有序链表 - 力扣&#xff08;LeetCode&#xff09; ok这次就简单点&#xff0c;大家自己去看题目了 将两个升序链表合并为一个…
阅读更多...
【Linux】进程的七大状态详解！

【Linux】进程的七大状态详解！

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …
阅读更多...
如何查看centos7中Java在哪些路径下

如何查看centos7中Java在哪些路径下

在 CentOS 7 上&#xff0c;你可以通过几种方式查找安装的 Java 版本及其路径。以下是一些常用的方法&#xff1a; 1. 使用 alternatives 命令 CentOS 使用 alternatives 系统来管理同一命令的多个版本。你可以使用以下命令来查看系统上所有 Java 安装的配置&#xff1a; su…
阅读更多...
C++动态内存管理：与C语言动态内存管理的差异之争

C++动态内存管理：与C语言动态内存管理的差异之争

当你改错一行代码的时候&#xff1a; 当你想要重构别人的代码时&#xff1a; 目录 前言 一、C/C的内存分布 二、C/C语言中的动态内存管理 三、new与delete的实现原理 总结&#xff1a; 前言 在C中&#xff0c;内存管理是一个至关重要的主题。正确地管理内存可以避免内存泄…
阅读更多...
上海AI Lab开源首个可替代GPT-4V的多模态大模型

上海AI Lab开源首个可替代GPT-4V的多模态大模型

与开源和闭源模型相比&#xff0c;InternVL 1.5 在 OCR、多模态、数学和多轮对话等 18 个基准测试中的 8 个中取得了最先进的结果。 上海AI Lab 推出的 InternVL 1.5 是一款开源的多模态大语言模型 (MLLM)&#xff0c;旨在弥合开源模型和专有商业模型在多模态理解方面的能力差距…
阅读更多...
二、SPI协议

二、SPI协议

文章目录 总述1.SPI接口2. SPI工作模式3. SPI通信时序4. SPI协议 对比 UART协议&#xff08;上一篇文章刚介绍过uart协议&#xff0c;这里来对比一下&#xff09; 总述 SPI&#xff08;Serial Peripheral Interface&#xff09;是一种高速的、全双工、同步的串行通信总线&…
阅读更多...
【影片欣赏】【指环王】【魔戒：国王归来 The Lord of the Rings: The Return of the King】

【影片欣赏】【指环王】【魔戒：国王归来 The Lord of the Rings: The Return of the King】

往期魔戒博客见&#xff1a; 【影片欣赏】【指环王】【魔戒&#xff1a;护戒使者 The Lord of the Rings: The Fellowship of the Ring】 【影片欣赏】【指环王】【魔戒&#xff1a;双塔奇谋 The Lord of the Rings: The Two Towers】 2004年发行&#xff0c;Special Extend…
阅读更多...
副业兼职没那么难，视频号带货，1天稳定500，适合新手操作

副业兼职没那么难，视频号带货，1天稳定500，适合新手操作

向大家推荐一个项目&#xff1a;视频号书单号带货玩法。我已经实践了一段时间&#xff0c;并成功售出了1200多单&#xff0c;赚取了2万多元。这个项目表现相当出色&#xff0c;强烈推荐给大家&#xff01; 周周近财&#xff1a;让网络小白少花冤枉钱&#xff0c;赚取第一桶金 …
阅读更多...
Linux vscode push报错fatal: Authentication failed

Linux vscode push报错fatal: Authentication failed

注意啊&#xff0c;Git基于密码的身份验证已经被删除了&#xff0c;所以这个报错发生时无论密码正确与否&#xff0c;以及参考比较旧的改bug教程&#xff0c;都没法提交。进入提示的网址&#xff0c;生成个人访问令牌就好了
阅读更多...
200-500人规模工厂网络方案（中小企业网络）

200-500人规模工厂网络方案（中小企业网络）

一、方案概述 工厂一般有单独的弱电房&#xff0c;类似这种 里面采用的方案如下&#xff1a; 主要考虑有线、无线、财务、办公、访客等业务&#xff0c;便于维护管理和后续扩容 还需要 Wi-Fi覆盖零死角高速率&#xff0c;工作不卡顿 同时考虑AV反病毒、IPS入侵防御、用户准…
阅读更多...
【MySQL数据库开发设计规范】之命名规范

【MySQL数据库开发设计规范】之命名规范

欢迎点开这篇文章&#xff0c;自我介绍一下哈&#xff0c;本人姑苏老陈 &#xff0c;是一名JAVA开发老兵。 本文收录于 《MySQL数据库开发设计规范》专栏中&#xff0c;该专栏主要分享一些关于MySQL数据库开发设计相关的技术规范文章&#xff0c;定期更新&#xff0c;欢迎关注&…
阅读更多...
python自动化生成ppt

python自动化生成ppt

使用Python和python-pptx创建PPT 在这篇博客中&#xff0c;我们将探讨如何使用Python库python-pptx来创建一个简单的PowerPoint演示文稿&#xff08;PPT&#xff09;。这个库允许我们以编程方式创建幻灯片、添加文本、图片、表格和自定义形状。 安装python-pptx 首先&#x…
阅读更多...
智能助手上线，大模型提供云服务专属顾问

智能助手上线，大模型提供云服务专属顾问

业务背景 在使用云服务的时候&#xff0c;当您遇到复杂问题&#xff0c;如配置、关联或计费方式不明确时&#xff0c;可能需要向客服提交工单进行技术沟通。在漫长的工作过程中&#xff0c;耗费了宝贵的时间和精力。 2024 年 4 月&#xff0c;百度智能云正式推出了融合文心大…
阅读更多...
单调栈：（C++）

单调栈：（C++）

在题目的要求中&#xff0c;存在先进后出&#xff08;即在前面的数据需要遍历到后面的某一数据时才能确定计算值&#xff09;单调栈在一部分解题场景中避免了暴力解法的高时间复杂度问题&#xff0c;但是在做题过程中视情况而定&#xff0c;有些题目的最优解不一定使用单调栈&a…
阅读更多...
【原创】springboot+mysql物资库存管理系统设计与实现

【原创】springboot+mysql物资库存管理系统设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…
阅读更多...
利用AI提高内容生产效率的五个方案

利用AI提高内容生产效率的五个方案

目录 如何利用AI提高内容生产效率? ​编辑方向一&#xff1a;自动化内容生成 方向二&#xff1a;内容分发与推广 方向三&#xff1a;内容分析与优化 方向四&#xff1a;图像和音频处理 方向五&#xff1a;自动编辑和校对 如何利用AI提高内容生产效率? 简介&#xff1a…
阅读更多...
车载电子电器架构 —— 应用软件开发(上)

车载电子电器架构 —— 应用软件开发(上)

车载电子电器架构 —— 应用软件开发(上) 我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。 老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 屏蔽力是信息过载时代一个人的特殊竞争力，任何消耗你的人和事，多看一眼都是你的不对。非必要不费力证明…
阅读更多...
最新文章

Copyright @ 2022~2023