【数据结构篇】探索堆的算法的巧妙

须知 

💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力!

👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力!
🚀 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++感兴趣的朋友,让我们一起进步!

接上篇:【初阶数据结构】实现顺序结构二叉树->堆(附源码)-CSDN博客 

上篇文章我们提及两个算法:向上调整算法和向下调整算法

哪个算法更高效?

1.向上调整算法时间复杂度

示例代码:

void AdjustUp(HPDataType* arr,int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)//不需要等于,child只要走到根节点的位置,根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//判断空间是否足够
	if (php->size == php->capacity)
	{
		//扩容
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = x;
	
	AdjustUp(php->arr, php->size);

	++php->size;
}
因为堆是完全⼆叉树,⽽满⼆叉树也是完全⼆叉树,此处为了简化使⽤满⼆叉树来证明(时间复杂度本
来看的就是近似值,多⼏个结点不影响最终结果)

1.1 分析:

 注:时间复杂度计算最坏情况下的次数,最差的情况就是堆中每个节点都要移动尽可能多的步数,可以得到下面计算公式:

则需要移动结点总的移动步数为:每层结点个数 * 向上调整次数(第⼀层调整次数为0)

上述使用错位相减求和。

根据大O渐进表示法得:
向上调整算法建堆时间复杂度为: O ( n ∗ log 2 n )  即 O(nlogn)
 2. 向下调整算法时间复杂度
堆的删除
删除堆是删除堆顶的数据,将 堆顶的数据根最后⼀个数据⼀换 ,然后删除数组最后⼀个数据,再进⾏向下调整算法。

步骤(如下图):

 

示例代码:

void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	//while (parent < n)
	while (child < n)
	{
		//找左右孩子中找最小的
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

注意:向下调整算法有⼀个前提:左右⼦树必须是⼀个堆,才能调整。

向下调整算法
将堆顶元素与堆中最后⼀个元素进⾏交换
删除堆中最后⼀个元素
将堆顶元素向下调整到满⾜堆特性为⽌
2.1 分析: 

 

3. 堆的应用

优先级队列的使用场景:包括定时任务轮训问题、合并有序小文件

求Top K值问题【使用一个堆解决】求中位数、百分位数

大数据量日志统计搜索排行榜

3.1 堆排序

堆排序是一种利用堆这种数据结构设计的排序算法

3.1.1 排序一 

使用现成数据结构->堆,将数据如堆,再取堆顶元素,在删除堆顶数据

// 1、需要堆的数据结构
// 2、空间复杂度 O(N)
void HeapSort1(int* a, int n)
{
 	HP hp;
    int arr1[6] = { 34,29,48,23,10,50 };
 	for(int i = 0; i < 6; i++)
	{
 		HPPush(&hp,a[i]);
 	}
     int i = 0;
     while (!HPEmpty(&hp))
     {
    	 a[i++] = HPTop(&hp);
     	HPPop(&hp);
     }
      HPDestroy(&hp);
 }

使用麻烦,同时代码量还多,效率低,不建议使用。

3.1.2 排序二

比如排升序:建大堆,为啥?

依次将堆顶最大的数据与最后一个(不断发生变化)元素交换,每次都是将最大的数据放最后,可以想象一下,就是升序了。

// 升序,建⼤堆
// 降序,建⼩堆
// O(N*logN)
void HeapSort2(int* arr, int n)
{
	int i = 0;
	for ( i = 0; i < n; i++)
	{
		HPAdjustUp(arr, i);
	}
	int end = n - 1;
	while (end)
	{
		Swap(&arr[0],&arr[end]);
		HPAdjustDown(arr, 0, end);
		end--;
	}
}

时间复杂度:O(nlogn)

3.1.3 排序三
void HeapSort3(int* arr, int n)
{
	for (int i =(n-1-1)/2 ; i >= 0; i--)
	{
		HPAdjustDown(arr, i, n);
	}
	int end = n - 1;
	while (end)
	{
		Swap(&arr[0], &arr[end]);
		HPAdjustDown(arr, 0, end);
		end--;
	}
}

建议使用向下调整算法建堆,原因:

移动多的步数节点少,移动少的步数节点多。

而向上调整算法:移动少的步数节点多,移动多的步数节点少。

显然少的步数少,次数就更少。

3.2 Top-k问题

TOP-K问题:即求数据结合中前K个最⼤的元素或者最⼩的元素,⼀般情况下数据量都⽐较⼤。

⽐如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题,能想到的最简单直接的⽅式就是排序,但是:如果数据量⾮常⼤,排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。

最佳的⽅式就是⽤堆来解决,基本思路如下:

⽤数据集合中前k个元素来建堆
前k个最⼤的元素,则建⼩堆;前k个最⼩的元素,则建⼤堆
⽤剩余的N-K个元素依次与堆顶元素来⽐较,不满⾜则替换堆顶元素 ,然后再将交换进去后的元素向下调整(保证这k个元素始终是堆),最后将剩余N-k个元素依次与堆顶元素⽐完之后,堆中剩余的K个元素就是所求的前k个最⼩或者最⼤的元素
代码如下:

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
void TOPk()
{
	int k = 0;
	printf("请输入k:");
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail!");
		exit(1);
	}
	int* minHeap = (int*)malloc(k * sizeof(int));
	if (minHeap == NULL)
	{
		perror("malloc fail!");
		exit(2);
	}

	//从文件中读取前K个数据
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}

	//建堆---小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		HPAdjustDown(minHeap, i, k);
	}

	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		//读取到的数据跟堆顶的数据进行比较
		//比堆顶值大,交换入堆
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			HPAdjustDown(minHeap, 0, k);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}

	fclose(fout);
}

int main()
{
	//CreateNDate();
	TOPk();
	return 0;
}

相信通过这篇文章你对堆排序的有了初步的了解。如果此篇文章对你学习数据结构有帮助,期待你的三连,你的支持就是我创作的动力!!!

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

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

相关文章

智能家居10G雷达感应开关模块,飞睿智能uA级别低功耗、超高灵敏度,瞬间响应快

在当今科技飞速发展的时代&#xff0c;智能家居已经逐渐成为人们生活中不可或缺的一部分。从智能灯光控制到智能家电的联动&#xff0c;每一个细节都在为我们的生活带来便利和舒适。而在众多智能家居产品中&#xff0c;10G 雷达感应开关模块以其独特的优势&#xff0c;正逐渐成…

如何使用VBA识别Excel中的“单元格中的图片”(2/2)

Excel 365升级了新功能&#xff0c;支持两种不同的插入图片方式&#xff1a; 放置在单元格中&#xff08;Place in cell&#xff09;&#xff0c;新功能&#xff0c;此操作插入的图片下文中简称为单元格中的图片。放置在单元格上&#xff08;Place over cell&#xff09;&…

Nature|用于无线监测颅内信号的植入式柔性超声波传感器(柔性传感/健康监测/植入式电子/水凝胶)

华中科技大学臧剑锋(Jianfeng Zang)、华中科技大学同济医学院附属协和医院姜晓兵(Xiaobing Jiang)和新加坡南洋理工大学陈晓东(Xiaodong Chen)团队,在《Nature》上发布了一篇题为“Injectable ultrasonic sensor for wireless monitoring of intracranial signals”的论…

FlaskFastAPIgunicornunicorn并发调用

Flask VS. FastAPI Flask和FastAPI是Python中两种流行的Web框架&#xff0c;它们各自具有不同的特点和适用场景。以下是它们之间的一些主要区别&#xff1a; 1. 框架类型 Flask&#xff1a;Flask是一个轻量级的微框架&#xff0c;适合构建小型到中型的Web应用。它灵活且易于扩展…

像`npm i`作为`npm install`的简写一样,使用`pdm i`作为`pdm install`的简写

只需安装插件pdm-plugin-i即可&#xff1a; pdm plugin add pdm-plugin-i 然后就可以愉快地pdm i了&#xff0c;例如&#xff1a; git clone https://github.com/waketzheng/fast-dev-cli cd fast-dev-cli python -m pip install --user pipx pipx install pdm pdm plugin a…

C#笔记——委托(2)

Unity定义好的委托 在Unity里使用委托时&#xff0c;除了上章讲的自定我委托&#xff0c;还可以使用Unity定义好的委托 Action 无参无返回值委托 Func<T> 泛型委托 返回指定类型 Action<T1, T2> 可以传多个参数的有参委托 无返回值 Func<T1, T2> 可…

【玉米叶部病害识别】Python+深度学习+人工智能+图像识别+CNN卷积神经网络算法+TensorFlow

一、介绍 玉米病害识别系统&#xff0c;本系统使用Python作为主要开发语言&#xff0c;通过收集了8种常见的玉米叶部病害图片数据集&#xff08;‘矮花叶病’, ‘健康’, ‘灰斑病一般’, ‘灰斑病严重’, ‘锈病一般’, ‘锈病严重’, ‘叶斑病一般’, ‘叶斑病严重’&#x…

供应商图纸外发:如何做到既安全又高效?

供应商跟合作伙伴、客户之间会涉及到图纸外发的场景&#xff0c;这是一个涉及数据安全、效率及合规性的重要环节。供应商图纸发送流程一般如下&#xff1a; 1.申请与审批 采购人员根据需要提出发放图纸的申请并提交审批&#xff1b; 采购部负责人审批发放申请&#xff0c;确…

【深度学习】时间序列预测、分类、异常检测、概率预测项目实战案例

说明&#xff1a;本专栏内容来自于个人学习笔记、以及相关项目的实践与总结。写作目的是为了让读者体会深度学习的独特魅力与无限潜力&#xff0c;以及在各行各业之中的应用与实践。因作者时间精力有限&#xff0c;难免有疏漏之处&#xff0c;期待与读者共同进步。 前言 在当今…

JZ2440开发板——LCD

以下内容源于韦东山嵌入式课程的学习与整理&#xff0c;如有侵权请告知删除。 之前在博文中学习过LCD&#xff08;SoC是S5PV210&#xff09;&#xff0c;作为对比&#xff0c;本文学习S3C2440这款SoC的LCD方面的内容。主要涉及以下三个内容&#xff1a; 一、LCD的硬件原理 1.…

2024 Rust现代实用教程:Ownership与结构体、枚举

文章目录 一、Rust的内存管理模型1.GC&#xff08;Stop the world&#xff09;2.C/C内存错误大全3.Rust的内存管理模型 二、String与&str1.String与&str如何选择2.Example 三、枚举与匹配模式1.常见的枚举类型&#xff1a;Option和Result2.匹配模式 四、结构体、方法、…

数据结构C语言描述1(图文结合)--顺序表讲解,实现,表达式求值应用,考研可看

前言 这个专栏将会用纯C实现常用的数据结构和简单的算法&#xff1b;用C基础即可跟着学习&#xff0c;代码均可运行&#xff1b;准备考研的也可跟着写&#xff0c;个人感觉&#xff0c;如果时间充裕&#xff0c;手写一遍比看书、刷题管用很多&#xff0c;这也是本人采用纯C语言…

Oracle视频基础1.3.7练习

1.3.7 看oracle是否启动构造一个pfile:boobooke.ora看spfilewilson内容修改alert log file里拷贝的参数内容&#xff0c;创建一个pfile boobooke.ora用新创建的pfile启动数据库&#xff0c;并创建新的spfile:spfilebbk.ora启动数据库&#xff0c;监听&#xff0c;看新的进程解…

数据转换 | Matlab基于SP符号递归图(Symbolic recurrence plots)一维数据转二维图像方法

目录 基本介绍程序设计参考资料获取方式 基本介绍 Matlab基于SP符号递归图&#xff08;Symbolic recurrence plots&#xff09;一维数据转二维图像方法 符号递归图(Symbolic recurrence plots)是一种一维时间序列转图像的技术&#xff0c;可用于平稳和非平稳数据集;对噪声具有…

将android studio3.4.1改为as 2024的方法

将android studio3.4.1改为as 2024的方法 先正常的open项目&#xff0c;不用等gradle build完&#xff0c;就先改这2个地方&#xff1a; 1.替换as2024新建一个空的正常的项目的build.gradle和config.gradle 2.在build.gradle(app)中 删除3处kotlin相关的提示&#xff08;2个…

【温酒笔记】DMA

参考文档&#xff1a;野火STM32F103 网友资料整理 1. Direct Memory Access-直接内存访问 DMA控制器独立于内核 是一个单独的外设 DMA1有7个通道DMA2有5个通道DMA有四个等级&#xff0c;非常高&#xff0c;高&#xff0c;中&#xff0c;低四个优先级如果优先等级相同&#xf…

Stable Diffusion Web UI 1.9.4常用插件扩展-WD14-tagger

Stable Diffusion Web UI 1.9.4 运行在 WSL 中的 Docker 容器中 tagger 插件的作用是&#xff0c;上传一张图片&#xff0c;反推这张图片可能的提示词。 使用场景就是&#xff0c;想要得到类似的图片内容时使用。 WD14-tagger 安装 Stable Diffusion WebUI WD14-tagger GitH…

VS 中使用c#高版本语言方法

方法如下&#xff0c;打开项目工程文件&#xff08;记事本&#xff09;&#xff0c;然后添加如下语句&#xff1a;保存&#xff0c;重新加载即可使用最新C#语法。

Golang--DOS命令、变量、基本数据类型、标识符

1、DOS命令 切换盘符&#xff08;大小写没有区别&#xff09;&#xff1a; c: //切换到c盘 d: //切换到d盘 e: //切换到e盘 显示文件内信息&#xff1a; 指令&#xff1a;dir 切换路径&#xff1a; 指令&#xff1a;cd 绝对路径 / 相对路径 . 表示当前…

正反向滤波的简述和MATLAB代码

文章目录 MATLAB 例程:卡尔曼滤波与反向滤波运行结果代码说明总结P.S. 相关公式1. 正向滤波(Forward Filtering)2. 反向滤波(Backward Filtering)3. 总结以下是一个简单的MATLAB例程,演示如何使用卡尔曼滤波进行状态估计,包括正向滤波和反向滤波的实现。这个例程模拟了一…