DS堆的实际应用(10)

文章目录

前言
一、堆排序
- 建堆
- 排序
二、TopK问题
- 原理
- 实战
- - 创建一个有一万个数的文件
  - 读取文件并将前k个数据创建小堆
  - 用剩余的N-K个元素依次与堆顶元素来比较
  - 将前k个数据打印出来并关闭文件
- 测试
三、堆的相关习题
总结

前言

学完了堆这个数据结构的概念和特性后，我们来看看它的实际运用吧！

一、堆排序

建堆

要学习堆排序，首先要学习堆的向下调整算法，因为要用堆排序，你首先得建堆，而建堆需要执行多次堆的向下调整算法

这是因为我们之前已经学过了，建堆时候向下调整算法时间复杂度为O(N)，向上调整算法为O(NlogN)

建堆有两种，一种是建大堆，另一种就是建小堆，假如我要升序排列，那么是要选择哪一种呢？

出人意料的是，我们选择建立大堆，这听起来很反常，但是没关系，我们后面再讲解~

我们前面也学了，向下调整对左子树和右子树是有要求的，必须同为小堆或者同为大堆，如果我们从头开始向下调整，就显然不符合这个规律了，于是我们转换策略，从倒数第一个非叶子节点开始向下调整

至于为啥不是最后一个节点，答案是最后一个节点乃至最后一层节点都是度为0的节点，左子树右子树都是空树，也可以理解成同样类型的堆

在这里插入图片描述

//建堆
//注意i的初始值，n-1是因为对应下标要减一
//再减一除二是因为最后一个节点的父节点必是倒数第一个非叶子节点
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}

排序

建完堆后，排序的思想如下：

将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但是调整时被交换到最后的那个最大的数不参与向下调整
完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下去，直到堆中只有一个数据时便结束。此时该序列就是一个升序

这个时候，你可能就能理解为什么升序建堆的时候使用的是大堆而不是小堆了，因为如果使用小堆，那么虽然第一个数是最小值，但是剩下的 n - 1 个数堆的结构被破坏了，得重新建堆，再选出次小，依次直到选出最大的那个数，屡次建堆带来的大量消耗是我们接受不了的

//升序 大堆
void HeapSort(int arr[], int size)
{
	assert(arr);
	//1.建堆 向上调整 O(N*logN)
	//for (int i = 1; i < size; i++)
	//{
	//	AdjustUp(arr, i);
	//}
	
	//1.向下调整建堆 O(N)
	//从第一个非叶子结点开始向下调整，一直到根
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, size, i);
	}
	
	//2.向下调整 O(N*logN)
	int end = size - 1;//记录堆的最后一个数据的下标
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);//将堆顶的数据和堆的最后一个数据交换
		AdjustDown(arr, end, 0);//对根进行一次向下调整
		end--;//堆的最后一个数据的下标减一
	}
}

二、TopK问题

原理

TOP-K问题：即求数据中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

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

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

用数据集合中前K个元素来建堆：

前k个最大的元素，则建小堆
前k个最小的元素，则建大堆

用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

经过上述两步后，此时堆中剩余的K个元素就是所求的前K个最小或者最大的元素

其实这里思路跟堆排序大差不差，主要就是利用堆顶的特性，如果需要找出最大值，那么在小堆（都是很大的值）中堆顶就相当于门槛，至少需要被最大中的最小要大才有资格进来，然后重新筛选出来新的最小值当保安

实战

假设我们现在要找出一千万个随机数中的前k个最大的数，数据太大，内存有限，我们先考虑第一步

创建一个有一万个数的文件

先来回顾一下以下文件函数：

//文件打开
FILE * fopen ( const char * filename, const char * mode );//前面参数为文件名 后面参数为文件打开方式
//文件关闭
int fclose ( FILE * stream );
int fprintf ( FILE * stream, const char * format, ... );//将后面函数写入的信息写入stream
int fscanf ( FILE * stream, const char * format, ... );//将stream的信息写入后面的函数

随机数的范围为0-32767。最多只有32768个，远小于一千万，为了减少随机数的重复，我们需要将随机数加上一个数，又因为单纯的使用srand不是真正的随机数，我们还需要加上time时间戳

//1.创造随机数到文件中
void CreateNDate()
{
	int n = 10000000;
	srand((unsigned int)time(NULL));
	FILE* pf = fopen("data.txt", "w");//以写的方式打开文件
	if (pf == NULL)
	{
		perror("fopen fail");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		//rand随机数有限制 只有几万个 所以+i
		int x = (rand() + i) % 10000000;
		fprintf(pf, "%d\n", x);//将数据写入文件中
	}
	fclose(pf);//关闭文件
	pf = NULL;//手动置空
}

读取文件并将前k个数据创建小堆

int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
	perror("malloc fail");
	return;
}
//1.读取文件前k个建小堆 
for (int i = 0; i < k; i++)
{
	fscanf(pf, "%d", &minheap[i]);
	AdjustUp(minheap, i);
}

用剩余的N-K个元素依次与堆顶元素来比较

//2.读取文件的数据与堆顶数据进行比较 如果大则 向下调整
int x = 0;
while (fscanf(pf, "%d", &x) != EOF)
{
	if (x > minheap[0])
	{
		minheap[0] = x;
		AdjustDown(minheap, k, 0);
	}
}

将前k个数据打印出来并关闭文件

//注意这里前k个数据并不一定成排序
//但是可以肯定这是所有N个数中最大的k个数
//minheap[0]又是这k个数中最小的一个
for (int i = 0; i < k; i++)
{
	printf("%d ", minheap[i]);
}
free(minheap);
fclose(pf);
pf = NULL;