大家好，我是苏貝，本篇博客带大家了解堆的TopK问题，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

---

一. 前言

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决

---

二. TopK

思路:

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

下面我们用找出1000000个元素中最大的5个值举例

1
为1000000个元素赋值

1000000个元素当然不可能是由我们手动赋值，我们想到有srand函数搭配time函数可以生成随机值。
以写的形式打开文件"data.txt"，如果文件不存在，就会建立该文件。
我们知道，srand(time(0))能生成的随机值只有3万多个，这就意味着如果我们只用随机数赋值的话，会有将近997万的数据是重复的，所以我们在随机数的基础上再加一个会变的数，这样重复的数字就会比较少。
最后，将随机数写入文件中。

void CreateData()
{
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	int n = 1000000;
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		int x = 0;
		x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

在上面代码的操作下，我们能保证所有的随机值都<1000000，那我们如何确保最后的结果是正确的呢？我们可以在执行完这个函数后，再打开文件，随意修改5个值，让它们都>1000000，这样最后的值只能是我们修改了的。

注意：
在修改完5个值后，将调用main函数中调用CreateData函数的代码注释掉，否则再次运行程序，文件里的数据会重新被修改

2
如何建小堆？

1.先定义一个指针指向k个元素的数组
2.将文件的前k个元素边插入，边向上调整，最后得到小堆

了解fscanf

//void swap(int* a, int* b)
//{
//	int tmp = *a;
//	*a = *b;
//	*b = tmp;
//}


//void AdjustUp(int* a, int child)
//{
//	assert(a);
//
//	int parent = (child - 1) / 2;
//	while (child > 0)
//	{
//		if (a[child] < a[parent])
//		{
//			swap(&a[child], &a[parent]);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		else
//			break;
//	}
//}
    FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
    //1.建有k个元素的小堆
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("fopen fail");
		return;
	}

	//2.将前k个元素插入小堆中
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
		AdjustUp(minheap, i);
	}

3
要找出最大的k个值时，为什么不用大堆？

因为如果最大值先出来，就占据了堆顶的位置，此时次大值就因为<最大值而不能进入大堆中。

4
得到TopK

用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素，再将新的堆顶元素向下调整

//void AdjustDown(int* a, int size, int parent)
//{
//	assert(a);
//
//	int child = parent * 2 + 1;
//	while (child < size)
//	{
//		if (child + 1 < size && a[child + 1] < a[child])
//		{
//			child++;
//		}
//		if (a[child] < a[parent])
//		{
//			swap(&a[child], &a[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//
//}

    //3.遍历，如果有数比堆顶元素大的话，让堆顶元素=该元素，再向下调整
	while (fscanf(fout, "r") != EOF)
	{
		int x = 0;
		fscanf(fout, "%d", &x);
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

---

三. 代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<time.h>


//构建数据
void CreateData()
{
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	int n = 1000000;
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		int x = 0;
		x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}


void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


void AdjustUp(int* a, int child)
{
	assert(a);

	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}


void AdjustDown(int* a, int size, int parent)
{
	assert(a);

	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && 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 PrintTopK(FILE* file, int k)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	//1.建有k个元素的小堆
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("fopen fail");
		return;
	}

	//2.将前k个元素插入小堆中
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
		AdjustUp(minheap, i);
	}

	//3.遍历，如果有数比堆顶元素大的话，让堆顶元素=该元素，再向下调整
	while (fscanf(fout, "r") != EOF)
	{
		int x = 0;
		fscanf(fout, "%d", &x);
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}

	free(minheap);
	fclose(fout);
}

//TopK 找出最大的k个值
int main()
{
	//CreateData();
	PrintTopK("data.txt", 5);
	return 0;
}

---

好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞👍吗，感谢看到这里，我们下篇博客见❤️