TOP-K问题

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

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

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

最佳的方式是用堆来解决，我们只需要对k个数据建堆，如果是求前k个最大的数，则建小堆，如果是求前k个最小的数，则建大堆。以求前k个最大的数为例，建好小堆后，堆顶元素是k个数据中最小的那个，然后我们依次将剩余的数与堆顶元素比较，如果大于堆顶元素就交换，然后再调整这k个元素，然后再比较，依此类推，最后当所有的数据都遍历完时，堆中的k个数据便是前k个最大的数据，这便是用堆来解决的思路。

我们首先要产生大量数据，一个一个去写是不可能的，所以我们先写一个产生随机数的函数。

void CreateNData()
{
	int n = 100000;

	srand(time(0));   
    //srand是一个函数，用于设置随机数生成器的种子值
    //time是一个函数，它返回从1970年1月1日（称为Unix纪元）开始到当前时间的秒数
    //当传入0作为参数给 time 函数时，它返回当前的时间

	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}

	for (int i = 0; i < n; i++)
	{
		int x = rand() % 100000;  //控制随机数的范围
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

接下来我们打开data.txt文件来看看：

此时，data.txt中已经产生了很多随机数了，并且都在0~100000之间。

为了方便后续我们验证所写程序确实能找出前k个（假定为10）最大的值，我们随机在10个数后边加上几个1使其大于100000，以便区分。

接下来实现找这k个数的函数：

void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	//读取k个数据放入开辟好的空间里
	int i = 0;
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	for (i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

	//向下调整法建小堆
	for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);  //在前两篇博客中已经写过了，这里就不再放代码了
	}

	//文件中其他数据与堆中最小数比较，大于则交换
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

	//打印
	for (i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	fclose(fout);
}

最后，我们测试一下，在主函数中调用PrintTopK：