双端队列和优先级队列

文章目录

  • 前言
  • deque
    • deque底层设计
    • 迭代器设计
  • priority
  • 仿函数
  • 数组中的第k个最大元素
  • 优先级队列模拟实现
    • push
    • pop
    • 调整
    • 仿函数
    • 存储自定义类型

前言

今天要介绍比较特殊的结构，双端队列。
还有一个适配器，优先级队列。

deque

在这里插入图片描述
栈的默认容器用了一个deque的东西，这个东西是啥?
deque虽然是队列，但它不是正队列，它是双端队列。

为什么叫双端队列，因为它最适合头插头删，尾插尾删。

deque对标的是vector+list.

它的结构和前面没有什么差别。
在这里插入图片描述

这些功能只有我们之前讲的list能做到。
在这里插入图片描述

最牛逼的是还有这个
在这里插入图片描述

看，它既支持vector的功能又支持list的功能。

但是这个东西真的这么牛吗？
要回答这个问题，我们得看一下deque的底层设计。

deque底层设计

我们先来分析一下顺序表和链表的区别。

顺序表：
它最大的优点就是空间连续随机访问，但是也带来了，头插，中间插入删除的困难。
在这里插入图片描述

其实顺序表还有一个优点就是高速缓存效率高，但是这里学习的时候不作为重点。

链表：
在这里插入图片描述

能不能把list和vector的优点合起来呢?
有人用了一个折中的思路。

折中的思路，一次开一个的小数组，满了以后在开一段空间，不扩容。
怎样管理多端小数组？中控（指针数组）
在这里插入图片描述

假设我要头插或者尾插
在这里插入图片描述

大家看这个结构什么时候需要扩容？
中控满了就需要扩容。但是扩容的代价低。因为中控扩容中只拷贝指针。

在这里插入图片描述

假设我要访问第25个数据，怎么访问？
在这里插入图片描述

小数组要不要扩容，这是很灵活的，得你自己去看

为什么它的扩容代价低?
相比vector而言，只需要拷贝指针，代价低了很多。
但相比list而言，还是比不过list,list没有扩容的概念，增加一个数据它就开一次空间。

在这里插入图片描述

注意，deque的随机访问比vector低，但是比list还是高很多。

在这里插入图片描述

deque适合干嘛？
头插头删多，尾插尾删多可以用。

大家可以去测试一下deque和vector和list sort的效率
其实效率都不如拷贝到vector,进行排序然后拷贝回去。

迭代器设计

它的迭代器设计是我们目前为止接触到最复杂的迭代器。
在这里插入图片描述
它有四个指针，看它们分别干嘛的？

在这里插入图片描述

cur:当前指向数据的位置
first和last:buff数组开始和结束
node:反向指向中控数组

在这里插入图片描述
好像也没有那么难理解。

这里就不模拟实现了，deque在现实生活中用的其实不多，除了用来做头插头删，做deque的默认容器以外，
实际当中用的还是vector和list.

如果对deque有兴趣可以去看一下源码，但其实没必要，有些东西我们需要深入学习，但deque我们只需要
了解它的框架就可以了。

priority

这个东西还是挺适用的，很多地方都要用。
在这里插入图片描述
默认容器是vector,当然你也可以传deque，但是这里deque不如vector.

它有个要求，就是随机访问的迭代器。

它是优先级队列，看一下接口就知道了。
在这里插入图片描述
它的接口跟我们的堆很想。

它这里需不需要符合先进先出？
不需要，它是要求优先级高的先出。

它也不支持遍历，容器适配器都不支持遍历。

还是出一个走一个。

void test_priority_queue()
{
//默认是大堆，大的优先级高
	priority_queue<int> pq;
	pq.push(1);
	pq.push(0);
	pq.push(5);
	pq.push(2);
	pq.push(1);
	pq.push(7);

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

在这里插入图片描述

它默认认为什么的优先级高？
大的优先级高。

它的底层是一个vector，vector的底层实际是一个堆，也就是一个完全二叉树。
默认是大堆。

那我现在有一个问题，以后要用topk的时候，还需要自己写一个堆出来吗？
不需要。

如果要变成小堆，怎么办？
用了一个仿函数。
在这里插入图片描述
这里用了一个less,默认是大堆。

// 小堆 -- 小的优先级高
priority_queue<int, vector<int>, greater<int>> pq;

包一下这个文件

#include <functional>

仿函数

假设我需要写一个大于或小于的仿函数，怎么写呢?
其实很简单， 仿函数都有一个特点，重载一个（）的运算符。
这个（）就是函数参数的括号的运算符。

在这里插入图片描述

如果但看这一行，你会觉得lessFunc是什么？

cout << lessFunc(1, 2) << endl;

函数名或者函数指针，但它其实是一个对象。
这个类叫做仿函数。表示它的对象可以像函数一样去使用。但它的本质是调用operator(), 是运算符重载。

仿函数有什么好处？
它的好处是能更好的去做类型。模拟实现优先级队列的时候能更好理解。
它的对象可以像函数一样调用，我们就可以控制很多行为。

C++搞出这个东西是由于函数指针太复杂了。具体是函数指针的类型太复杂了。有些地方是要去做回调。

C的qsort
在这里插入图片描述
C++的sort
在这里插入图片描述
把上面的仿函数更改为针对任意类型。

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

int main()
{
	Less<int> lessFunc;
	cout << lessFunc(1, 2) << endl;
	return 0;
}

下面我们用优先级队列来做一个题目

数组中的第k个最大元素

数组中的第k个最大元素
在这里插入图片描述

在这里插入图片描述
返回第k个最大元素，好不好找？
排序就搞定了。
在这里插入图片描述

但是时间复杂度不满足
这道题最好的方式肯定还是快排的思想，我们这里不考虑这个，我们把堆用起来。

如果这道题优先级队列来解决,怎么解决?
在这里插入图片描述

pop k次，堆顶的元素就是我们要找的元素。
这样写，时间复杂度是多少？
第四行的时间复杂度是多少?N
我们知道向下建堆可以O(N).

pop的时间复杂是多少？
K*logN

所以合计的时间复杂度。
O(KlogN+N)
这里如果k==N,那就麻烦了，时间复杂度是NlogN

假设N远大于k,且N很大，有什么优化方式？
我们要找最大的前k个，除了全部建大堆，还有没有其他方式？

我们还可以建k个元素的堆。

那我们建大堆还是小堆？
Top k最大的前k个，我们是要建小堆。

看代码
在这里插入图片描述
这样解决时间复杂度是多少？
在这里插入图片描述

它最大的特点是消耗空间很小。

我们学会了优先级队列，根本不需要去手搓一个堆

优先级队列模拟实现

在这里插入图片描述

首先，底层要存数据还是用vector这样的东西来存.

接着我们在把要写的接口给写出来，这跟栈还是很像的。
在这里插入图片描述

push

想一想堆是怎么push数据的？
堆的底层是一个数组的结构。我们插入数据的时候向上调整。
在这里插入图片描述
在这里插入图片描述

pop

堆的数据删除怎么删？
堆的删除直接删，不然堆就挪乱了。效率极低。
堆删除数据是删除第一个数据，将第一个数据和最后一个数据交换，然后删除最后一个数据，然后从根开始向下调整。
在这里插入图片描述
在这里插入图片描述

调整

怎呢向上调整？
跟父结点比，挨着挨着往上走就可以了。
先搞大堆。
在这里插入图片描述

template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		void adjust_up(int child)
		{
			Comapre com;

			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;
				}
			}
		}

		void adjust_down(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				Comapre com;

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

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

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

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

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

快速写了一个优先级队列，测试一下，自己写的代码。

在这里插入图片描述
在这里插入图片描述

它的适配器默认是vector，这里用deque,但是它照样能跑。
也就是说这里你只需要符合它的需求，满足上面的接口，这个程序都可以正常运行。

它们的底层已经天差地别了，一个是vector,一个是双端队列，但是对这个上层的优先级队列完全没有影响。这就是容器适配器，只要你那个东西满足我的需求，我就可以转换成我想要的东西。

仿函数

上面写的是大堆的代码，那我要变成小堆呢？
要变成小堆，就要控制上面调整的比较方式。
在这里插入图片描述

总不能纯手搓吧。我们肯定是先把大堆写出来，加东西，然后顺便改一下就变成小堆了。
那这一定是外部可以传一个东西去控制，它这里是通过模板参数去控制的。

怎么通过模板参数来控制呢？
先写两个可以比较的仿函数。
在这里插入图片描述
那就可以用这个类型的对象去比较。

//跟库里面保持一致，大堆用一个小于。
template<class T, class Container = vector<T>,  class Compare = less<T>>

神奇的事情发生了。
大堆和小堆就可以随意更换了。

void adjust_up(int child)
{
	Comapre com;

	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//if (_con[parent] < _con[child])
		if (com(_con[parent], _con[child]))
		//if (Comapre()(_con[parent], _con[child]))
		{
			swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void adjust_down(int parent)
{
	size_t child = parent * 2 + 1;
	while (child < _con.size())
	{
		Comapre com;

		//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[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

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

以前用的泛型是控制数据类型，不知道具体的数据类型是什么，你传什么就是什么。
现在控制的不是类型，控制的是比较方式。默认它是less,那com就是less对象，less对象去调用operator()，那它就是小于比较方式。
在这里插入图片描述
它能够通过模板参数传类型，类型里面实例化对象控制比较的方式。

跟函数指针的比较
模板传的是类型，仿函数是一个类。类型就可以在模板参数传，模板参数传有什么好处？
我整个类都可以用。

仿函数还有其他功能，我们在后面会C++的学习中会慢慢感受到

存储自定义类型

假设我们优先级数列存储的数据不再是内置类型。自定义类型，能不能用优先级队列。
也可以。

大堆：
在这里插入图片描述
在这里插入图片描述

小堆：
在这里插入图片描述
在这里插入图片描述

日期类需要重载大于，小于才行。
如果没有重载就需要写仿函数才能搞定。
在这里插入图片描述

给大家看一下更牛逼的东西。
在这里插入图片描述

结果每次都不一样
在这里插入图片描述

怎么回事呢？
现在存进去的T是Date*,不是Date.
Date* 可以进行比较，但这不是我想要的。
Date* 是new出来的，new是堆上申请的空间，那个地址可能先大先小，完全没有规律。

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

如果我非要这样比较呢？
我们的骚操作又要上场了。

默认是大堆。
在这里插入图片描述
在这里插入图片描述
再怎么运行他都不会变。
在这里插入图片描述

小堆：
再写一个仿函数
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这是不是给了一个非常大的空间
它真正的优势在于，我就是个compare对象，有个默认比较方式，但是你想要其他的比较方式，全部都可以交给你控制。你想怎么比就怎么比。

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

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

相关文章

福德机械：植保无人机的领航者

福德机械：植保无人机的领航者

亲爱的读者们&#xff0c;欢迎来到福德机械的神奇世界。在这个充满活力和创新的世界里&#xff0c;我们专注于植保无人机的发展与应用&#xff0c;以实现农业现代化、智能化和高效化的目标。植保无人机&#xff0c;作为一种高效、环保和安全的农业工具&#xff0c;已经逐渐成为…
阅读更多...
自动化测试流程详解

自动化测试流程详解

最近很多小伙伴问我自动化测试到底该怎么做&#xff1f;流程是什么样的&#xff1f;在每个阶段都需要注意什么&#xff1f;本文也就主要从自动化测试的基本流程入手&#xff0c;对面试自动化测试工程师的同学会有不少帮助。对于在职的朋友&#xff0c;也可以参考此流程&#xf…
阅读更多...
速锐得解码适配新能源纯电动汽车比亚迪E3车型CAN矩阵协议

速锐得解码适配新能源纯电动汽车比亚迪E3车型CAN矩阵协议

在新能源电动汽车中王牌有特斯拉&#xff0c;王朝有比亚迪。在国内&#xff0c;比亚迪顺风顺水&#xff0c;能见度最高的王朝系列拥有EV、双模以及燃油三种能源类型&#xff0c;攻占着全国不同的市场&#xff0c;性价比高的&#xff0c;属于E系列&#xff0c;早期的E6是整个出租…
阅读更多...
vue3-在使用el-form编辑的时候会出现在修改表单值的时候在列表出现值也相对应的更新

vue3-在使用el-form编辑的时候会出现在修改表单值的时候在列表出现值也相对应的更新

这里我犯了一个错误&#xff0c;就是使用reactive来定义声明响应式状态&#xff0c;下面是reactive的局限性&#xff0c;不能替换整个编辑的对象的&#xff0c;所以&#xff0c;我们在这里要使用ref来声明响应式状态
阅读更多...
机器学习可重复性危机下，创建复杂数据系统的挑战

机器学习可重复性危机下，创建复杂数据系统的挑战

文章目录 一、前言二、主要内容三、总结 &#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 一、前言 数据科学系统已成为众多研究领域的关键性工具&#xff0c;其开发者群体呈现出多元化的背景特征。在过去十年中&#xff0c;尽管数据科学与机器学习的强…
阅读更多...
python语言的官方网站地址,python语言官方网站网址

python语言的官方网站地址,python语言官方网站网址

大家好&#xff0c;给大家分享一下python语言的官方网站地址&#xff0c;很多人还不知道这一点。下面详细解释一下。现在让我们来看看&#xff01; Python官方网站地址及源代码 Python是一种高级编程语言&#xff0c;广泛应用于各个领域&#xff0c;包括软件开发、数据分析、人…
阅读更多...
[PyTorch][chapter 7][李宏毅深度学习][深度学习简介]

[PyTorch][chapter 7][李宏毅深度学习][深度学习简介]

前言&#xff1a; 深度学习常用的开发平台 TensorFlow torch theano caffe DSSTNE mxnet libdnn CNTK 目录&#xff1a; 1&#xff1a; 深度学习发展历史 2&#xff1a; DeepLearning 工程简介 3&#xff1a; DNN 简介 一 发展历史 二 DeepLearning 工程简介 深度学习三…
阅读更多...
自动化测试知识总结

自动化测试知识总结

一、自动化测试 自动化测试的定义&#xff1a;使用一种自动化测试工具来验证各种软件测试的需求&#xff0c;它包括测试活动的管理与实施、测试脚本的开发与执行。 自动化测试只是测试工作的一部分&#xff0c;是对手工测试的一种补充; 自动化测试绝不能代替手工测试;多数情况…
阅读更多...
ohpm : 无法将“ohpm”项识别为 cmdlet、函数...

ohpm : 无法将“ohpm”项识别为 cmdlet、函数...

这是因为没有在环境变量里配置 Ohpm. 左上角File->Settings,找到Ohpm放的路径 bin目录下&#xff0c;然后复制 此电脑->右键属性->高级系统设置->环境变量->系统变量找到Path,添加刚才复制的那一行 重启 DevEco ,在Terminal输入 ohpm -v ,出现版本号就欧了 如果…
阅读更多...
MAC下加载动态库

MAC下加载动态库

MAC引用动态库时报错&#xff1a; 查看一个可执行文件或者动态库引用的第三方库路径&#xff1a;otool -L xxx.dylib 第一行是动态库的安装名称&#xff08;INSTALL Name&#xff09;。当另一个客户端链接到这个 dylib 时&#xff0c;dylib 的安装 ID 会被复制到客户端中作为…
阅读更多...
一文解析数据结构是如何装入 CPU 寄存器的？

一文解析数据结构是如何装入 CPU 寄存器的？

我们在之前很多文章的讲解中涉及了CPU与寄存器&#xff0c;然后有同学问了这样一个问题&#xff1a;既然CPU内部的寄存器数量有限&#xff0c;容量有限&#xff0c;那么我们使用的庞大的数据结构是怎样装入寄存器供CPU计算的呢&#xff1f;这篇文章就为你讲解一下这个问题。 内…
阅读更多...
【Bug修复】秒杀服务器异常，轻松恢复网站访问--从防火墙到Docker服务的全面解析

【Bug修复】秒杀服务器异常，轻松恢复网站访问--从防火墙到Docker服务的全面解析

&#xff08;秒杀方案&#xff09;服务器异常&#xff1a;connection is closed by foreign host… 月初部署了一个私人项目到服务器上&#xff0c;刚开始还能用&#xff0c;用了不到两天报了上面的错误&#xff1a;connection is closed by foreign host… &#x1f33a;问题描…
阅读更多...
基于ssm学院学生论坛的设计与实现论文

基于ssm学院学生论坛的设计与实现论文

摘 要 网络的覆盖&#xff0c;电脑手机的普及使得人们的交流上升到网络信息化的层面上来&#xff0c;论坛系统就是在这样的环境下就诞生了&#xff0c;而且深受用户喜爱。 本学院学生论坛系统应用Java技术&#xff0c;MYSQL数据库存储数据&#xff0c;基于SSMVue框架开发。在网…
阅读更多...
C++类-派生类

C++类-派生类

类之间的关系 类之间的三种关系&#xff1a; 包含关系&#xff1a;class B{ private: A a;}使用关系&#xff1a;class B{public: void method(A &a);}继承关系&#xff1a;class B: public A{} 继承 继承允许我们依据另一个类来定义一个类&#xff0c;这使得创建和维护…
阅读更多...
浏览器输入URL再按下回车会经历哪些过程

浏览器输入URL再按下回车会经历哪些过程

目录 前言 一、解析URL 二、解析域名(DNS) 三、TCP三次握手建立连接 1.seq、syn、ack含义 2.三次握手 四、发送http/https请求 五、服务器响应请求 六、浏览器解析渲染页面 七、TCP四次挥手断开连接 总结 前言 看各种面经发现这个问题是一个高频出现的面试问题&#xff0c;但…
阅读更多...
Physically-Based Rendering(PBR)基于物理的渲染（一）

Physically-Based Rendering(PBR)基于物理的渲染（一）

文章目录 一、什么是PBR? 一、什么是PBR? Physically-Based Rendering (PBR)基于物理渲染包含材质、光源、相机、光线传播等&#xff0c;但在实时渲染领域我们提PBR说的就是PBR材质。 PBR在实时领域材质丰富度没有离线PBR多&#xff0c;因为要考虑性能。 再者严格来说实时领…
阅读更多...
【网络协议】LACP（Link Aggregation Control Protocol，链路聚合控制协议）

【网络协议】LACP（Link Aggregation Control Protocol，链路聚合控制协议）

文章目录 LACP名词解释LACP工作原理互发LACPDU报文确定主动端确定活动链路链路切换 LACP和PAgP有什么区别&#xff1f;LACP与LAG的关系LACP模式更优于手动模式LACP模式对数据传输更加稳定和可靠LACP模式对聚合链路组的故障检测更加准确和有效 推荐阅读 LACP名词解释 LACP&…
阅读更多...
云贝教育 |【分享课】12月14日周四PostgreSQL分享主题：PG的流复制

云贝教育 |【分享课】12月14日周四PostgreSQL分享主题：PG的流复制

分享主题&#xff1a;PG的流复制 讲师&#xff1a;刘峰 时间&#xff1a;12月14日 周四 晚上 19:30 分享平台&#xff1a;微信视频号 云贝学院 分享内容&#xff1a; 流复制的工作原理流复制主从搭建流复制主从切换流复制添加/删除备节点流复制修改同步模式
阅读更多...
工作随记：oracle 19c客户端通过service访问PDB异常问题

工作随记：oracle 19c客户端通过service访问PDB异常问题

文章目录 概要技术测试分析测试1&#xff1a;测试2&#xff1a;测试3&#xff1a;测试4&#xff1a; 解决方案&#xff1a;1、修改service2、修改pdb名称 总结 概要 应用端访问提示错误信息为&#xff1a;VersionHelper异常!未将对象引用设置到对象的实例&#xff01; 此问题…
阅读更多...
Axure产品流程图绘制

Axure产品流程图绘制

1.Axure产品流程图绘制简介 2.获取软件 2.1 ProcessOn介绍 2.2 ProcessOn应用场景 3.绘制门诊模块流程图 3.1 门诊模块流程图 4.绘制住院业务流程图 4.1 住院业务流程图 5.药库采购入库流程图 5.1 药库采购入库流程图 6.会议OA流程图 6.1 会议OA流程图 7.自定义元件…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站