💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

💥个人主页：大耳朵土土垚的博客
💥 所属专栏：数据结构学习笔记 、C语言系列函数实现
💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

🥳🥳前面我们学习了利用堆进行排序，今天我们将继续介绍利用堆解决前k个最值的问题，Topk问题（==在N个数中找出最大的前k个==）在实际生活中也非常常见，💥💥比如店外卖时评分最高的前十家店铺，玩王者时英雄战力前十名等与排序排名有关的应用。

🥰🥰***解题思路***

正常思路 将这N个数建成一个大堆，然后Popk次，就可以找出最大的前k个 ；
💫💫但是如果N非常大以亿计（10亿个整数所占空间大概4G）那么就会非常耗时耗力，难以计算。

这里给出一种更好的解决办法：

①将前k个数建成小堆；（必须是小堆哦~）
②后面N-k个数依次比较，如果比堆顶的数据大，就替换它进堆；
③然后将替换后的再向下调整使之重新成为一个小堆；
④最后这个小堆的值就是最大的前k个。

在写题之前我们先要创造N个数，可以通过c语言的文件操作以及随机生成函数来获得并写入文件中：

代码如下：

#include<time.h>
//创造N个数据
void CreatData()
{
	//造数据
	int n = 1000;
	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() % 10000;
		fprintf(fin, "%d\n", x);
		
	}
	fclose(fin);
}

✨✨这里使用了srand生成随机数需要包含time.h头文件；
int x = rand() % 10000;这个式子可以帮助我们生成10000以内的随机数；
fprintf可以帮助我们将生成的随机数写入到文件中（如下图生成了data文件）：

所以生成文件后为了找到最大的前k个，我们可以手动改一些数据来验证后续代码的正确性：

这里手动改了5个，后面如果找出这五个最大的数就说明我们写的代码是正确的啦~🥳🥳
为了保证文件数据不被覆盖，我们在运行一次CreatData()函数之后就可以把它屏蔽掉了，此时已经生成了n个数据的文件data.txt了。

int main()
{
	
	//CreatData();//屏蔽
	PrintTopk(5, 1000);

	return 0;
}

Topk排序

造完数据后我们就可以利用之前学习过的堆来求出Topk啦

代码如下：

void PrintTopk(int k,int n)
{
	//打开文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
	//创建顺序表开辟空间
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	//从文件中读取k个数
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}
	//将读取的k个数创建为小堆
	//堆向下调整算法
	for (int i = (k - 2) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}
	//将剩余N-k个数依次与堆顶元素比较
	for (int i = 0; i < n - k; i++)
	{
		int tmp = 0;
		fscanf(fout, "%d", &tmp);
		if (tmp > kminheap[0])
		{
			Swap(&tmp, &kminheap[0]);
			AdjustDown(kminheap, k, 0);
		}
	}
	//打印前k个元素
	for (int i = 0; i < k; i++)
	{
		printf("%d\n", kminheap[i]);
	}
}

对于造小堆以及排序有疑问的可以看看土土的上篇博客🥰🥰——堆排序详解

运行代码如下：

int main()
{
	
	//CreatData();
	PrintTopk(5, 1000);

	return 0;
}

运行结果如下：

🎉🎉完全正确~是我们之前改的那五个数，说明我们的代码将它从1000个数中找了出来🥳🥳至此Topk问题得到解决 ~

✨✨这里再提一句，打印出来的虽然是n个数中的最大的k个但是我们发现打印的顺序是乱的，通过之前排序的学习，大家知道怎么将他们按顺序打印出来吗？有兴趣的小伙伴可以尝试一下~🥳🥳

结语

以上就是数据结构中利用堆排序求解Topk问题啦，关键在于对于堆排序的理解与运用~有疑问的小伙伴可以将问题打在评论区或者私信我哦 ~完结撒花 ~🥳🥳🎉🎉🎉