[数据结构初阶]堆的应用

各位读者老爷好,鼠鼠又来了捏!鼠鼠上一篇博客介绍的堆,那么今天来浅谈以下堆的应用,那么好,我们先来看两个问题:

1.如果有一组乱序的数组数据,希望你将这组数组的数据排成升序或降序,该怎么排?

2.如果有1万个乱序的数据,希望你找出其中最大的前5个,该这么找到捏?


目录

1.堆排序

1.1.堆排序代码 

1.2.向下调整建堆法

 1.3.堆排序的优势

2.Top_K 问题

2.1.Top_K问题代码 

 2.2.办法3优势

3.ending


对于问题1,当然可以使用冒泡排序,但是冒泡排序的时间复杂度是O(N^2),显然不是一个很好的方法!鼠鼠我呀在这里介绍一个解决办法:堆排序!堆排序的时间复杂度是O(N*logN),相对于解决办法之冒泡排序好用的不是一星半点捏!

1.堆排序

要注意堆排序是对数组本身进行排序。上一篇博客中的运行结果似乎也将数据排好序了,但数组本身没有排好序,是额外开辟了空间取数组成员全部入堆后再循环取堆顶数据并删除堆顶数据而成的,这样子不是真正的堆排序。

堆排序即利用堆的思想来进行排序,总共分为两个步骤:
1. 建堆
升序:建大堆
降序:建小堆
2. 利用堆删除思想来进行排序

1.1.堆排序代码 

这篇博客我们以排降序为例讲解堆排序: 

本鼠先把堆排序(降序)的代码呈现如下,老爷们有兴趣看看啊:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

typedef int HeapDataType;


//交换
void Swap(HeapDataType* a, HeapDataType* b)
{
	HeapDataType tmp = *a;
	*a = *b;
	*b = tmp;
}


//向上调整(小堆)
void AdjustUp(HeapDataType* a, int childcoordinate)
{
	int parentcoordinate = (childcoordinate - 1) / 2;
	while (childcoordinate > 0)
	{
		if (a[parentcoordinate] > a[childcoordinate])
		{
			Swap(&a[parentcoordinate], &a[childcoordinate]);
			childcoordinate = parentcoordinate;
			parentcoordinate = (parentcoordinate - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


//向下调整(小堆)
void AdjustDown(HeapDataType* a, int parentcoordinate, int HeapSize)
{
	int childcoordinate = parentcoordinate * 2 + 1;
	while (childcoordinate < HeapSize)
	{
		if (a[childcoordinate] > a[childcoordinate + 1] && childcoordinate + 1 < HeapSize)
		{
			childcoordinate++;
		}
		if (a[parentcoordinate] > a[childcoordinate])
		{
			Swap(&a[parentcoordinate], &a[childcoordinate]);
			parentcoordinate = childcoordinate;
			childcoordinate = childcoordinate * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//堆排序排降序
void HeapSort(HeapDataType* a, int HeapSize)
{
	int i = 0;

	//排降序,建小堆(向上调整建堆法)
	for (i = 1; i < HeapSize; i++)
	{
		AdjustUp(a, i);
	}
	int end = HeapSize - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
}


int main()
{
	int a[] = { 90,80,60,20,40,70,60,30,30,110 };
	int Size = sizeof(a) / sizeof(a[0]);
	printf("堆排序前:");
	for (int i = 0; i < Size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	HeapSort(a, Size);
	printf("堆排序后:");
	for (int i = 0; i < Size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

也许各位老爷对于这些个代码有点懵懵的,没关系,鼠鼠我来一点点分析上面代码:

首先我们来看这几个函数:

//交换
void Swap(HeapDataType* a, HeapDataType* b)
{
	HeapDataType tmp = *a;
	*a = *b;
	*b = tmp;
}


//向上调整(小堆)
void AdjustUp(HeapDataType* a, int childcoordinate)
{
	int parentcoordinate = (childcoordinate - 1) / 2;
	while (childcoordinate > 0)
	{
		if (a[parentcoordinate] > a[childcoordinate])
		{
			Swap(&a[parentcoordinate], &a[childcoordinate]);
			childcoordinate = parentcoordinate;
			parentcoordinate = (parentcoordinate - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


//向下调整(小堆)
void AdjustDown(HeapDataType* a, int parentcoordinate, int HeapSize)
{
	int childcoordinate = parentcoordinate * 2 + 1;
	while (childcoordinate < HeapSize)
	{
		if (a[childcoordinate] > a[childcoordinate + 1] && childcoordinate + 1 < HeapSize)
		{
			childcoordinate++;
		}
		if (a[parentcoordinate] > a[childcoordinate])
		{
			Swap(&a[parentcoordinate], &a[childcoordinate]);
			parentcoordinate = childcoordinate;
			childcoordinate = childcoordinate * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

这几个函数上一篇博客已经介绍过了,分别是交换函数、向上调整函数和向下调整函数。只不过这里的向上调整函数和向下调整函数是服务小堆,而上一篇博客的向上调整函数和向下调整函数是服务大堆的,但是基本思想是不变的,这里鼠鼠就不多说了!

我们再来看下一个函数:

//堆排序排降序
void HeapSort(HeapDataType* a, int HeapSize)
{
	int i = 0;

	//排降序,建小堆(向上调整建堆法)
	for (i = 1; i < HeapSize; i++)
	{
		AdjustUp(a, i);
	}
	int end = HeapSize - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
}

这个函数就是堆排序函数了,排的是降序。参数a是待排序数组的指针,HeapSize是待排序数组(以下简称数组)的数据个数。

堆排序是这样子的:

 1.建堆。首先我们先将数组本身建成小堆。这里我们采用向上调整建堆法,用一个for循环调用向上调整函数将待排序数组本身变成小堆。这里本质模拟的是堆插入的过程建堆。

2.利用堆删除思想来进行排序。数组已经是小堆了,那么堆顶的数据一定是最小的数据,我们再将堆顶数据与数组尾部数据交换,这样子数组尾部数据就是最小的,再调用向下调整函数将数组前HeapSize-1个数据成小堆;然后我们再将由前HeapSize-1个数据构成的小堆的堆顶数据(这个数据是次小的)与由前HeapSize-1个数据构成的小堆的最后一个数据(也就是数组倒数第二个数据)交换,这样子数组倒数第二个数据就是次小的,然后我们再调用向下调整函数将数组前HeapSize-2个数据成小堆…………这样就可以将数组数据变成降序的。

我们看运行结果确实是没问题的:

1.2.向下调整建堆法

上面堆排序的代码中我们第一步是将待排序数组建成小堆,我们用的是向上调整建堆法,其实我们还可以用向下调整建堆法。

就像这样:

//堆排序排降序
void HeapSort(HeapDataType* a, int HeapSize)
{
	int i = 0;

	//排降序,建小堆(向下调整建堆法)
	for (i = (HeapSize-1-1)/2;i>=0;i--)
	{
		AdjustDown(a,i,HeapSize);
	}
	int end = HeapSize - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
}

向下调整建堆法的思想就是先找到以数组尾部数据的父节点(这个父节点下标假设为n)为根的树,将这颗树用向下调整函数调成小堆,再将以下标为n-1的节点为跟的树用向下调整函数调成小堆,再将以下标为n-2的节点为跟的树用向下调整函数调成小堆……再将以下标为0的节点为跟的树用向下调整函数调成小堆那么整个数组数据就成了一个小堆。

用向下调整建堆法的堆排序完整代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

typedef int HeapDataType;


//交换
void Swap(HeapDataType* a, HeapDataType* b)
{
	HeapDataType tmp = *a;
	*a = *b;
	*b = tmp;
}


//向下调整(小堆)
void AdjustDown(HeapDataType* a, int parentcoordinate, int HeapSize)
{
	int childcoordinate = parentcoordinate * 2 + 1;
	while (childcoordinate < HeapSize)
	{
		if (a[childcoordinate] > a[childcoordinate + 1] && childcoordinate + 1 < HeapSize)
		{
			childcoordinate++;
		}
		if (a[parentcoordinate] > a[childcoordinate])
		{
			Swap(&a[parentcoordinate], &a[childcoordinate]);
			parentcoordinate = childcoordinate;
			childcoordinate = childcoordinate * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//堆排序排降序
void HeapSort(HeapDataType* a, int HeapSize)
{
	int i = 0;
	//排降序,建小堆(向下调整建堆法)
	for (i = (HeapSize-1-1)/2;i>=0;i--)
	{
		AdjustDown(a,i,HeapSize);
	}
	int end = HeapSize - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
}


int main()
{
	int a[] = { 90,80,60,20,40,70,60,30,30,110 };
	int Size = sizeof(a) / sizeof(a[0]);
	printf("堆排序前:");
	for (int i = 0; i < Size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	HeapSort(a, Size);
	printf("堆排序后:");
	for (int i = 0; i < Size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

 运行结果是没问题的,跟上面用向上调整建堆法的堆排序结果一模一样。

这里用向下调整建堆法的堆排序是有以下优势的,所以我们写堆排序可以采用向下调整建堆法更佳:

1.堆排序的两个步骤都用向下调整函数即可,不必多写一个向上调整函数。

2.向上调整建堆法的时间复杂度是O(N*logN),而向下调整建堆法的时间复杂度是O(N),至于这些个复杂度为什么是这样子的鼠鼠就不证明了。

 1.3.堆排序的优势

堆排序的时间复杂度是O(N*logN),为啥复杂度是这个,鼠鼠不证明了!如果有100万个乱序数据让我们排序的话,笼统的说,我们用堆排序要排2千万次,如果用冒泡排序的话我们要排1万亿次。


对于问题2,我们可以用以下方法解决:

1.利用上一篇博客实现的堆,将1万个数据依次插入堆中构成大堆,再循环5次操作:取堆顶数据并删除堆顶数据。这样子取出来的5个堆顶数据就是最大的前5个数据。这个方法的时间复杂度是O(N*logN),空间复杂度是O(N)。

2.利用上面堆排序,将1万个数据排成降序,再取前5个数据就是最大的前5个数据。这个方法的时间复杂度是O(N*logN),空间复杂度是O(1)。

3.读取1万个数据的前5个数据,将这5个数据本身建立成小堆,再依次取剩余的9千9百9十5个数据与小堆堆顶数据比较,如果大于堆顶数据就替换堆顶数据并再次利用向下调整函数再成堆,比较完剩余的9千9百9十5个数据后,小堆里面的数据就是最大的前5个数。这种方法就引出鼠鼠要介绍的堆的应用之Top_K问题。

2.Top_K 问题

 TOP-K问题:即求数据集合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大(就是说从N个数据中求最大或最小的前K个数据,N远大于K)。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

1.如果求最大的前K个数据:

取前k个元素,建小堆。用剩余的N-K个元素依次与堆顶元素来比较,如果大于堆顶元素替换堆顶元素并利用向下调整函数再成堆,剩余N-K个元素比较完后,堆中剩余的K个元素就是最大的前K个数。

2.如果求最小的前K个数据:

取前k个元素,建大堆。用剩余的N-K个元素依次与堆顶元素来比较,如果小于堆顶元素替换堆顶元素并利用向下调整函数再成堆,剩余N-K个元素比较完后,堆中剩余的K个元素就是最小的前K个数。

2.1.Top_K问题代码 

思路我们解释完了,我们看一下代码:

鼠鼠用10万个随机数找出最大的前5个数为例子测试用堆来解决思路的可行性

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

typedef int HeapDataType;

//交换
void Swap(HeapDataType* a, HeapDataType* b)
{
	HeapDataType tmp = *a;
	*a = *b;
	*b = tmp;
}


//向上调整(小堆)
void AdjustUp(HeapDataType* a, int childcoordinate)
{
	int parentcoordinate = (childcoordinate - 1) / 2;
	while (childcoordinate > 0)
	{
		if (a[parentcoordinate] > a[childcoordinate])
		{
			Swap(&a[parentcoordinate], &a[childcoordinate]);
			childcoordinate = parentcoordinate;
			parentcoordinate = (parentcoordinate - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


//向下调整(小堆)
void AdjustDown(HeapDataType* a, int parentcoordinate, int HeapSize)
{
	int childcoordinate = parentcoordinate * 2 + 1;
	while (childcoordinate < HeapSize)
	{
		if (a[childcoordinate] > a[childcoordinate + 1] && childcoordinate + 1 < HeapSize)
		{
			childcoordinate++;
		}
		if (a[parentcoordinate] > a[childcoordinate])
		{
			Swap(&a[parentcoordinate], &a[childcoordinate]);
			parentcoordinate = childcoordinate;
			childcoordinate = childcoordinate * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//找大的前K个数
void PrintfTop_K(HeapDataType* a, int Size, int K)
{
	HeapDataType* minheap = (HeapDataType*)malloc(sizeof(HeapDataType) * K);
	if (minheap == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int i = 0;
	//取a前K个数并建小堆
	for (i = 0; i < K; i++)
	{
		minheap[i] = a[i];
		AdjustUp(minheap, i);
	}
	int X = K;
	for (X; X < Size; X++)
	{
		if (a[X] > minheap[0])
		{
			minheap[0] = a[X];
			AdjustDown(minheap, 0, K);
		}
	}
	for (i = 0; i < K; i++)
	{
		printf("%d ", minheap[i]);
	}
	free(minheap);
}


int main()
{
	int Size = 100000;
	HeapDataType* a = (HeapDataType*)malloc(sizeof(HeapDataType) * Size);
	srand((unsigned int)time(0));
	for (int i = 0; i < Size; i++)
	{
		a[i] = (rand() + i) % 100000;
	}
	//打入5个探子,将这5个探子的值更改成大于100000
	a[9] = 110000;
	a[99] = 111000;
	a[999] = 111100;
	a[9999] = 111110;
	a[99999] = 11111111;
	PrintfTop_K(a, Size, 5);
	free(a);
	a = NULL;
	return 0;
}

看结果我们确实将5个探子找出来了,就是最大的前5个数:

 2.2.办法3优势

我们再分析以下:

对于问题2的解决办法1来说,我们都需要将数据加载到内存中才行 ,如果加载的数据量太大的话,这个方法就行不通。比如有1百亿个int类型的数据要全部加载到内存的话差不多要40GB。而且如果磁盘中数据太多的话效率不高。

对于问题2的解决办法2来说,我们基于堆排序的思想确实可以在磁盘中拿数据对磁盘中的数据本身进行排序,但是如果磁盘中数据太多的话效率不高。

对于问题2的解决办法3来说,是最好的解决办法,首先时间复杂度是O(N*logK),一般K都很小,那么时间复杂度就是O(N),空间复杂度很明显是O(1)。

3.ending

鼠鼠我才疏学浅,上面的博客难免有错误,恳请读者老爷发现后指出,鼠鼠我很期待各位老爷的斧正呢!

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

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

相关文章

【Spring MVC】快速学习使用Spring MVC的注解及三层架构

&#x1f493; 博客主页&#xff1a;从零开始的-CodeNinja之路 ⏩ 收录文章&#xff1a;【Spring MVC】快速学习使用Spring MVC的注解及三层架构 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 Spring Web MVC一: 什么是Spring Web MVC&#xff1…

大促销活动时期如何做好DDoS防护?

每一次活动大促带来的迅猛流量&#xff0c;对技术人而言都是一次严峻考验。如果在活动期间遭受黑产恶意DDoS攻击&#xff0c;无疑是雪上加霜。电商的特性是业务常态下通常不会遭受大流量DDoS攻击&#xff0c;且对延迟敏感&#xff0c;因此只需要在活动期间按需使用DDoS防护。本…

分享three.js实现乐高小汽车

前言 Web脚本语言JavaScript入门容易&#xff0c;但是想要熟练掌握却需要几年的学习与实践&#xff0c;还要在弱类型开发语言中习惯于使用模块来构建你的代码&#xff0c;就像小时候玩的乐高积木一样。 应用程序的模块化理念&#xff0c;通过将实现隐藏在一个简单的接口后面&a…

代码随想录第二十四天| 回溯算法P1 | ● 理论基础 ● 77.

● 理论基础 题目分类 什么是回溯法 回溯法也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 在二叉树系列中&#xff0c;不止一次提到了回溯&#xff0c;如二叉树&#xff1a;以为使用了递归&#xff0c;其实还隐藏着回溯 (opens new window)。 回溯是递归的副产品&…

通过pymysql读取数据库中表格并保存到excel(实用篇)

本篇文章是通过pymysql将本地数据库中的指定表格保存到excel的操作。 这里我们假设本地已经安装了对应的数据库管理工具&#xff0c;里面有一个指定的表格&#xff0c;现在通过python程序&#xff0c;通过调用pymysql进行读取并保存到excel中。 关于数据库管理工具是Navicat P…

使用Python简单筛选excel表数据并写入到新表

文章目录 0 背景1 技术2 实现代码 0 背景 因为需要检索excel中的一些信息&#xff0c;把检索后的结果&#xff0c;写入到新表中。 符合筛选后的结果&#xff1a; 写入到的新表格数据&#xff1a; 1 技术 使用pandas库&#xff0c;读取excel表格的数据。然后对表格中的数据…

初始Java篇(JavaSE基础语法)(5)(类和对象(下))

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 目录 封装 访问限定符 封装扩展之包 自定义包 static成员 static修饰成员变量 static修饰成员方法 static成员变量初始化 内部类 对象的打…

leetcode131分割回文串

递归树 下面这个代码是遍历处所有的子串 #include <bits/stdc.h> using namespace std; class Solution { public:vector<vector<string>> vvs;vector<string> vs;vector<vector<string>> partition(string s) {dfs(0,s);return vvs;}vo…

使用Thymeleaf配置国际化页面

在国际化&#xff08;i18n&#xff0c;即 Internationalization 的缩写&#xff0c;其中“i”和“n”之间有18个字母&#xff09;的上下文中&#xff0c;Thymeleaf 和 Spring Boot 可以很容易地一起工作&#xff0c;以支持多种语言的页面显示。下面是如何在 Spring Boot 应用中…

Unix中的进程和线程-1

目录 1.如何创建一个进程 2.如何终止进程 2.2遗言函数 3.进程资源的回收 4.孤儿进程和僵尸进程 孤儿进程 (Orphan Process)&#xff1a; 僵尸进程 (Zombie Process)&#xff1a; 代码示例&#xff1a; 5. 进程映像的更新 在Linux中&#xff0c;进程和线程是操作系统进行工作调…

文件名目录名或卷标语法不正确:数据恢复策略与预防措施

一、文件名目录名或卷标语法不正确的现象 在日常使用电脑或移动设备时&#xff0c;我们经常会遇到“文件名目录名或卷标语法不正确”的错误提示。这种错误通常发生在尝试访问、修改或删除文件、目录或卷标时&#xff0c;系统会提示无法完成操作&#xff0c;因为文件名、目录名…

星云曲库测试报告

文章目录 一、项目介绍1.1项目背景1.2功能介绍 二、测试环境三、测试执行过程3.1功能测试3.1.1登录页面测试3.1.2歌曲列表页面测试3.1.3“我喜欢”页面测试3.1.4上传页面测试 3.2界面自动化测试3.2.1登录页面测试3.2.2歌曲列表页面测试3.2.3“我喜欢”页面测试3.2.4上传页面测试…

Unity TrailRenderer的基本了解

在Unity中&#xff0c;TrailRenderer组件用于在对象移动时创建轨迹效果。通常用于增强游戏中的动态物体&#xff0c;比如子弹、飞行道具或者角色移动时的拖尾效果。 下面来了解下它的基本信息。 1、创建 法1&#xff1a;通过代码创建 using UnityEngine;public class Trail…

css3之3D转换transform

css3之3D转换 一.特点二.坐标系三.3D移动&#xff08;translate3d)1.概念2.透视&#xff08;perpective)(近大远小&#xff09;&#xff08;写在父盒子上&#xff09; 四.3D旋转&#xff08;rotate3d)1.概念2.左手准则3.呈现&#xff08;transfrom-style)&#xff08;写父级盒子…

精品PPT-2023年无人驾驶汽车车联网网络安全方案

以下是部分PPT内容&#xff0c;请您参阅。如需下载完整PPTX文件&#xff0c;请前往星球获取&#xff1a; 无人驾驶安全架构是一个复杂的系统&#xff0c;它涉及到多个关键组件和层次&#xff0c;以确保无人驾驶车辆在各种情况下都能安全、可靠地运行。以下是一些主要的无人驾驶…

并查集

本文用于个人算法竞赛学习&#xff0c;仅供参考 目录 一.什么是并查集 二.并查集实现 三.路径优化 四.时间复杂度 五.并查集路径压缩 模板 五.题目 一.什么是并查集 并查集&#xff08;Disjoint Set&#xff09;是一种数据结构&#xff0c;用于处理一系列不相交的集合的合…

javaIO

file类 一个File类的对象可以表示一个具体的文件或目录 mkdir 创建单级文件夹 mkdirs 创建多级文件夹 delete 删除一个文件夹时&#xff0c;文件夹里面必须是空的 listfiles 将文件夹的子集放到一个file类型的数组中 输入及输出的概念 输入input 输出output 把jav…

pyinstaller打包多线程pyqt5程序后,报错,反复弹窗等问题

报错1&#xff1a; Traceback (most recent call last): File “MPL.py”, line 502, in File “Lib\site-packages\PyInstaller\hooks\rthooks\pyi_rth_multiprocessing.py”, line 45, in _freeze_support ValueError: not enough values to unpack (expected 2, got 1) 报…

STM32学习笔记(10_3)- 软件I2C读写MPU6050

无人问津也好&#xff0c;技不如人也罢&#xff0c;都应静下心来&#xff0c;去做该做的事。 最近在学STM32&#xff0c;所以也开贴记录一下主要内容&#xff0c;省的过目即忘。视频教程为江科大&#xff08;改名江协科技&#xff09;&#xff0c;网站jiangxiekeji.com 本期开…

分布式之分布式事务详解

分布式事务与实战运用 什么是分布式事务&#xff1f; 业务场景&#xff1a;用户A转账100元给用户B&#xff0c;这个业务比较简单&#xff0c;具体的步骤&#xff1a; 1、用户A的账户先扣除100元 2、再把用户B的账户加100元 如果在同一个数据库中进行&#xff0c;事务可以保证…