TopK问题在这里有多种解决的办法，我们取最优解：

1. 对N个数据进行从小到大或者从大到小排序，然后取出前K个数据便是我们想要找的数据。

2. 联想我们学过的堆排序，将这N个数建立大堆或者小堆，依次取出前K个数据即可。

但是这两种方法都存在一个问题：首先排序本身就是比较费劲的事情，如果N非常大，排序需要的代价很大，并且将N个数建堆也不合理，因为数据过多计算机内存容纳不下那么多的数据，就会存储到磁盘文件中，我们知道数据在磁盘文件中处理的速度是比较慢的，因此我们需要想一个更方便的方法（假设要在N个数据中找前K个最大的数据）。

改进方法：

1. 先建立K个数的小堆

2. 再用后面N-K个数依次插入，如果比堆顶的数据大，就替换进堆

3. 最后这个小堆中的数据就是要找的前K个数。

3.代码演示

3.1创建数据

我们为了来演示代码的正确性，我们先来创建数据，将10W个数据先保存在一个文件中，然后找出这10W个数据中最大的前五个数据。这里就需要用到文件操作的相关知识（进阶C语言：文件操作）和一个随机数的种子（猜数字小游戏）。

代码演示：
//创建数据
void CreateNDate()
{
	int n = 100000;           //总数据个数
 	srand((unsigned int)time(NULL));  //设置随机数生成器
	const char* file = "data.txt";
	//打开文件
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fial");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		//数据范围在10W之内
		int x = rand() % 100000;
		//写文件
		fprintf(fin, "%d\n", x);
	}
	//关闭文件
	fclose(fin);
	fin = NULL;
}

3.2建小堆、排序

先建K个数的小堆，然后使用剩下的N-K个数据依次插入比较，比堆顶大的数据就替换进堆,然后向下调整，直到将文件中的所有数据比较完成，这时这个K个数的堆就是我们要找的数据（这里建小堆为什么不建大堆？因为小堆的堆顶的元素是这个堆中最小的元素，如果有比它大的就可以筛选进入堆，如果建成大堆，那么堆顶的数就是最大的，那么遇到次大的就进不来，所以需要建小堆）。

代码演示：
void PrintTopK(int k)
{
	//打开文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fial");
		return;
	}
	//先建立K个数的小堆
	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 - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}
 
	int num = 0;
	//文件读取结束表示排序完成
	while (!feof(fout))
	{
		//依次比较
		fscanf(fout, "%d", &num);
		//符合则进行替换，向下调整
		if (num > kminheap[0])
		{
			kminheap[0] = num;
			AdjustDown(kminheap, k, 0);
		}
	}
 
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
 
	//关闭文件
	fclose(fout);
	fout = NULL;
}

4.完整代码


#define _CRT_SECURE_NO_WARNINGS 1
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
 
//Top - K问题
 
//交换函数
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
//向下调整
void AdjustDown(int* a, int n, int parent)
{
	//假设左孩子为左右孩子中最小的节点
	int child = parent * 2 + 1;
 
	while (child < n)  //当交换到最后一个孩子节点就停止
	{
		if (child + 1 < n  //判断是否存在右孩子
			&& a[child + 1] < a[child]) //判断假设的左孩子是否为最小的孩子
		{
			child++;   //若不符合就转化为右孩子
		}
		//判断孩子和父亲的大小关系
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//更新父亲和孩子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
//创建数据
void CreateNDate()
{
	int n = 100000;           //总数据个数
 	srand((unsigned int)time(NULL));  //设置随机数生成器
	const char* file = "data.txt";
	//打开文件
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fial");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		//数据范围在10W之内
		int x = rand() % 100000;
		//写文件
		fprintf(fin, "%d\n", x);
	}
	//关闭文件
	fclose(fin);
	fin = NULL;
}
 
void PrintTopK(int k)
{
	//打开文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fial");
		return;
	}
	//先建立K个数的小堆
	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 - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}
 
	int num = 0;
	//文件读取结束表示排序完成
	while (!feof(fout))
	{
		//依次比较
		fscanf(fout, "%d", &num);
		//符合则进行替换，向下调整
		if (num > kminheap[0])
		{
			kminheap[0] = num;
			AdjustDown(kminheap, k, 0);
		}
	}
 
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
 
	//关闭文件
	fclose(fout);
	fout = NULL;
}
 
int main()
{
	//创建数据
	CreateNDate();
	//求前5个最大数
	PrintTopK(5);
	return 0;
}

可以看到在10W个数据中找到了前5个最大的数。

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/716745

堆的应用：Top-K问题_topk问题 堆

前言：

1.何为Top-K

2.解题思路

3.代码演示

3.1创建数据

3.2建小堆、排序

4.完整代码

堆的应用：Top-K问题_topk问题堆