• 堆的使用（堆排序和Top-K问题）

    🐱作者：一只大喵咪1201
    🐱专栏：《数据结构与算法》
    🔥格言：你只管努力，剩下的交给时间！
    请添加图片描述

    堆的应用

    👨‍👦‍👦堆排序

    在上一篇文章二叉树——堆中实现向堆中插入和删除数据的时候，本喵详细的讲解了俩个算法，向上调整和向下调整。

    🧞‍♂️向上调整和向下调整的时间复杂度

    而且本喵还利用向上调整建了一个堆用来演示，同样的向下调整也是可以建堆的，既然向上调整和向下调整都可以建堆，那么它们之间有什么不同呢？那一个更好呢？

    接下来本喵就给大家计算一下向上调整和向下调整的时间复杂度。

    向上调整：

    计算时间复杂度就要按最坏的情况来算，假设一棵满二叉树，深度是h，每个节点都需要向上调整到根部

    图
    图中就是向上调整时间复杂度计算的全过程，结果是O(N*logN)。

    向下调整：

    同样按最坏的情况，整个满二叉树的所有节点都需要向下调整到最后一层

    图
    图中就是向下调整时间复杂度计算的全过程，结果是O(N)。

    经过这么一计算，俩个算法的效率高下立见，其中向下调整的算法是比向上调整更效率高的。

    原因：

    • 向下调整算法中，二叉树的最后一层是不用继续向下调整的，又由于最后一层的节点个数占了整棵树的一半，所以需要调整的节点减少了，效率也就上来了。
    • 向下调整算法中，节点数越多的层，需要向下调整的层数也就越少，而向上调整算法中，节点数越多的层，需要向上调整的层数也就越多。

    🧞‍♂️代码实现

    根据上面的分析，毫无疑问我们要采用时间复杂度为O(N)的向下调整的算法，
    但是向下调整是有条件的

    图
    像这样的堆是无法直接从头使用向下调整的。

    使用向下调整的前提：除了父节点外的俩个子树必须仍然同时符合小根堆或者大根堆。

    1. 重新建堆

    对于这样的堆，我们使用向下调整的算法倒着调整就可以重新建堆，也就是从最后一个叶子节点依次向前，每个节点都使用向下调整，这样调整过后整个堆就变成小根堆或者大根堆了。

    我们以建小根堆为例：

    请添加图片描述

    上面动图中

    • 向下调整法建堆从第一个叶子节点开始调整，也就是从红色框框住的8开始
    • 调整完这个节点后，顺序向前找一个节点，也就是绿色框框住的25，进行向下调整
    • 依次类推，从第一个非叶子节点开始向下调整，直到堆顶节点向下调整结束，此时一个小根堆就建立出来了
      图
    1. 交换并向下调整

    现在已经将一组数据建立成小堆了，毫无疑问，堆顶的数据是最小的，我们将堆顶是数据和堆的最后一个数据交换

    图

    此时堆最后一个位置的数据是最小的数据。

    再进行一次向下调整

    图
    此时除了最小值1以外其他数据又重新形成了小根堆。

    • 重复执行第二步直到所有的值都执行完，堆中的数据就会按照从大到小的顺序在数组和堆中排列

    图
    如此一来，就成功的将这组数据按照降序排列了

    有没有注意到，我们在建堆的时候，建的是小根堆，排出来的数据是降序的，所以我们可以得出结论：

    • 升序：建大堆
    • 降序：建小堆

    所以堆排序的步骤就是

    1. 重新建堆
    2. 交换并且向下调整
    3. 重复第2步

    接下来我们来看看代码是如何实现的。

    void HeapSort(int* a, int n)
{
	//重新建堆
	//降序排列，向下调整建小堆
	int i = (n - 1 - 1) / 2;//找到第一个叶子节点
	
	//建堆
	for (; i >= 0; i--)
	{
		//向下调整
		AdjustDown(a, n, i);
	}

	//交换并且向下调整
	i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);//交换
		AdjustDown(a, n - i, 0);//除最后一个树，其他数从堆顶向下调整
		i++;//排好个数加1
	}
}
void HeapSortTest()
{
	int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };
	int sz = sizeof(a) / sizeof(a[0]);
	HeapSort(a, sz);

	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	HeapSortTest();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    图
    得到的数组是降序排列的。

    注意：
    图

    • 红色框中，n-1表示的是最后一个元素的下标，(n-1-1)/2是为了找第一个叶子节点的坐标
    • 绿色框中，i–表示从第一个叶子节点开始前面的每个节点都进行一次向下调整
    • 蓝色框中，除交换后最后位置的元素外，其余元素将堆顶向下调整，以便形成新的小根堆

    如果想实现升序的排列，只需要重新建堆的时候建大根堆就好，其他照旧。

    堆排序是一种很牛逼的排序算法，我们来分析一下它的时间复杂度

    • 重新建堆的过程时间复杂度是O(N)，因为我们采用的是向下调整建堆
    • 交换以后每将堆顶的元素向下调整一次的时间复杂度是O(logN)
    • 需要排序的数据是N个，所以时间复杂度是O(N*logN)
    • 按照本喵在时间复杂度计算的文章中的计算方法，可以忽略掉重新建堆的时间复杂度O(N)
    • 所以堆排序的时间复杂度是O(N*logN)

    👨‍👦‍👦Top-K问题

    Top-K问题：

    • 即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

    比如：专业前10名、世界500强、富豪榜、游戏中前1 00的活跃玩家等。

    解决思路：

    1. 排序

    对于Top-K问题，能想到的最简单直接的方式就是排序。

    我们将一组数据排序成有序的，然后取其中的前K个就可以解决这个Top-K问题，这时我们刚刚学习的堆排序就派上了用场。

    1. 堆选数

    但是，如果此时有100亿个数据呢？还能排序吗？

    大致计算一下就知道，100亿个数据是400亿个字节，也就是占大约4GB的内存空间，我们的内存中根本没有这么大的空间，所以这么多的数据通常都是存放在硬盘上的。

    我们学习的堆排序包括其他排序，处理的都是内存中的数据，此时磁盘中的数据怎么处理呢？

    分批次运到内存中然后排序吗？显然是行不通的。

    所以对于大批量数据的Top-K问题，我们需要利用堆选数的方式来解决。

    堆选数的思路:

    图
    假设这里有100亿个数据，我们要选出前K个最大的数。

    • 建立一个能存放K个数的小堆
    • 将剩下的N-K个数与堆顶的数比较，凡是比堆顶大的数就入堆，并且进行向下调整，保持小堆结构不变
    • 当所有数据比完以后，小堆中的数据就是前K个最大的数

    这里我们可以将堆顶的数据看作是一个看门的小弟，堆中的其他数据都是它的大哥，外面来的人只有比这个小弟厉害才能去挑战大哥，如果外面来的这个人比其中一个大哥厉害，那么被打败的这个大哥就顶替小弟看门的位置，当作堆顶。

    下面我们就来实现一下，如何将硬盘中的数据选出前K个最大的

    首先创建100万个int类型的数据放在硬盘中

    void CreateData(char* filename, int N)
{
	assert(filename);

	FILE* fp = fopen(filename, "w");//以写的方式创建文件夹
	//判断是否打开成功
	if (fp == NULL)
	{
		perror("fopen fail");
		return;
	}
	//创建数据
	srand((unsigned int)time(NULL));
	for (int i = 0; i < N; i++)
	{
		fprintf(fp,"%d ", rand());
	}
	//关闭文件
	fclose(fp);
	fp = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    图
    可以看到这里有密密麻麻非常多的数字，这些数字是随机生成的。

    有了数据以后，我们就要利用堆选法选出最大的前K个数了。

    这里本喵将程序拆开来写。

    1. 首先要从文件中读取K个数
    assert(filename);

	FILE* pf = fopen(filename, "r");//以读的方式打开文件
	//判断是否打开成功
	if (pf == NULL)
	{
		perror("fopen fail");
		return;
	}

	//重建容量为K的小堆
	int* minHeap = (int*)malloc(sizeof(int) * K);//开辟K个空间的动态内存
	if (minHeap == NULL)
	{
		perror("malloc fail");
		exit(-1);//开辟失败，直接退出程序
	}
	//从文件中读取K个数字
	for (int i = 0; i < K; i++)
	{
		fscanf(pf, "%d", &minHeap[i]);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    此时我们开辟的空间，也就是堆中已经有K个数据，但并不是按照小堆的方式存放的。

    1. 将这K个数据重建成小根堆
    //向下调整建小堆
	for (int j = (K - 1 - 1) / 2; j >= 0; j--)
	{
		AdjustDown(minHeap, K, j);//向小调整
	}

    • 1
    • 2
    • 3
    • 4
    • 5

    这里采用向下调整重建小根堆

    1. 从文件中读取剩下的N-K个数并且与堆顶进行比较
    	//读取后面的N-K个数与堆顶比较
	int val = 0;
	while (fscanf(pf, "%d", &val) != EOF)
	{
		//判断值是否比堆顶大
		if (val > minHeap[0])
		{
			minHeap[0] = val;//改变堆顶的值
			AdjustDown(minHeap, K, 0);//向下调整保持小堆结构
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    每从文件中读取一个数据就与堆顶相比较，如果比堆顶的数据大，那就替换堆顶的数据，并且将堆重新向下调整一次，保证是小根堆的结构。

    1. 打印前K个最大的数
    	//打印前K个数
	for (int i = 0; i < K; i++)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");

	//关闭文件
	fclose(pf);
	pf = NULL;	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    图
    此时我们便求出了最大的前K个数。

    展示下完整的代码：

    void PrintTop_k(char* filename, int K)
{
	assert(filename);

	FILE* pf = fopen(filename, "r");//以读的方式打开文件
	//判断是否打开成功
	if (pf == NULL)
	{
		perror("fopen fail");
		return;
	}

	//重建容量为K的小堆
	int* minHeap = (int*)malloc(sizeof(int) * K);//开辟K个空间的动态内存
	if (minHeap == NULL)
	{
		perror("malloc fail");
		exit(-1);//开辟失败，直接退出程序
	}
	//从文件中读取K个数字
	for (int i = 0; i < K; i++)
	{
		fscanf(pf, "%d", &minHeap[i]);
	}
	//向下调整建小堆
	for (int j = (K - 1 - 1) / 2; j >= 0; j--)
	{
		AdjustDown(minHeap, K, j);//向小调整
	}

	//读取后面的N-K个数与堆顶比较
	int val = 0;
	while (fscanf(pf, "%d", &val) != EOF)
	{
		//判断值是否比堆顶大
		if (val > minHeap[0])
		{
			minHeap[0] = val;//改变堆顶的值
			AdjustDown(minHeap, K, 0);//向下调整保持小堆结构
		}
	}

	//打印前K个数
	for (int i = 0; i < K; i++)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");

	//关闭文件
	fclose(pf);
	pf = NULL;	
}
void Top_KTest()
{
	char filename[] = "Data.txt";//记录文件名

	int N = 1000000;//创建100万个数据

	int K = 10;//找前10个最大的数

	//CreateData(filename, N);
	PrintTop_k(filename, K);
}
int main()
{
	Top_KTest();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    那么我们到底要怎么确定我们找的前K个最大的数对不对呢？

    我们将所有的随机数控制在10000以内

    fprintf(pf,"%d ", rand() % 10000);

    • 1

    将生成随机数的语句改成这样，就将随机数控制在了10000以内。

    然后生成随机数文件。

    图
    可以看到，此时文件中的数据全部都是小于10000的数据

    • 我们在任意位置插入十个数，从10001到10010

    然后在插入数据的文件中找前K个最大的数。

    再运行程序

    图
    可以看到，我们找到的数据是正确的，就是我们插入的那10个最大的数字。

    此时Top-K的问题就解决了，接下来我们分析一下这个算法的时间复杂度和空间复杂度。

    时间复杂度

    • 在建立小堆的时，时间复杂度是O(K)
    • 进行一次比较后向下调整的时间复杂度是O(logK)，由于有N-K个数据，所以将所有数据比较并且调整完后的时间复杂度是(N-K)*logK
    • 总的时间复杂度就是O(K+(N-K)*ogK)

    空间复杂度

    只有在建堆的时候开辟了K个额外的空间，所以空间复杂度是O(K)

    👨‍👦‍👦总结

    以上便是堆的俩个应用，堆排序和解决Top-K问题，本喵提醒一下，我们这里来用到的向下调整是直接调用的函数，这个函数的实现逻辑在上一篇文章二叉树——堆中有详细讲解，还不熟悉的小伙伴可以移步去看看。希望对大家有所帮助。

  • 相关阅读:
    LeetCode75——Day15
    wps要会员才能把pdf分开，这不纯属智商税吗
    【Hadoop】7、HBase组件配置
    Dubbo中的Triple协议和应用级服务发现
    爬虫反爬：JS逆向实战2
    diffusers-Tasks
    【chromium】windows 获取源码到本地
    获得店铺的所有商品 API 返回值说明
    06 【函数（下）】
    易基因｜ctDNA甲基化测序分析（ctDNA-WGBS）用于癌症检测和分子分型 | 精准医学
  • 原文地址：https://blog.csdn.net/weixin_63726869/article/details/126283490