【数据结构初阶】--- 堆的应用：topk

堆的功能：topk

为什么使用topk

先举个例子，假如说全国有十万家奶茶店，我现在想找到评分前十的店铺，现在应该怎么实现？
第一想法当然是排序，由大到小排序好，前十就能拿到了。这是一种方法，但我觉得不太方便，因为我要排序就得需要数组先去存放这十万个数据，如果是100w，或是一亿个数据呢，这个时候要用4亿个字节存放这些数据，4亿个字节大概是多少内存我们来算算，1G == 1024MB == 1024*1024KB ==1024*1024*1024byte == 10亿。1G能存放10亿个字节，那么4亿个字节差不多就是400MB，你要对这些数据进行排序就需要400MB，空间的代价显而易见，很多情况下这些数据并不是在一个内存里存放着，而是在文件中，文件中的内容是存放在硬盘中的，因为硬盘空间大，而内存相比之下就很小。那么想拿到这些数据中最大的前十个，步骤也就是，将文件中的数据读取在从内存中开辟好的空间，再进行排序，找到前十个数。总而言之，直接排序会有很大的空间消耗。

什么是topk

接下来我来讲解topk是什么

1. 把前k个数建成小堆
2. 后面N-k个数，依次比较，如果比堆顶数据大，就替换他进堆
3. 最后这个小堆的值就是最大的前k个

思路：

我想要在这些数据中找到前十个最大的数，那我就先向内存中开辟十个数的空间，再读取前十个数（文件中最前面的十个数），同时将这是个数构建成一个小堆，之后从文件中每读取一个数据都与堆顶元素比较，如果大于堆顶元素，就用当前读取到的数覆盖这个堆顶元素，再进行向下调整；如果小于对顶元素那就读下一个数据，一直重复到结束，最终，小堆中的是个元素就是所有数据中最大的十个数。

验证加演示如何应用

1. 先创建一个文件“test.txt”
2. 生成10000个小于一万的数，并且写入到文件中

void CreateNData()
{
	Heap hp;
	HeapInit(&hp);
	srand((unsigned int)time(NULL));

	char* file = "test.txt";
	FILE* pf = fopen(file, "w");
	if (pf == NULL)
	{
		perror("fopen");
		return;
	}
	for (int i = 0; i < 10000; i++)
	{
		int x = rand() % 10000;
		fprintf(pf, "%d\n", x);
	}

	fclose(pf);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 打开文件，现在文件中已经有了随机生成的一万个数
   
4. 我们现在要找这一万个数中最大的前五个，为了清楚是哪五个数，我们手动修改五个数让它们变成最大，方便观看，我就挨着调整了5个数
   
5. 此时我们就要实现一个topk的功能，先建立一个大小为5的小堆，再将文件中每一个数据与堆顶元素比较，如果大于堆顶元素就取代该堆顶元素，再进行向下调整

void PrintTopk(int k)
{
	char* file = "test.txt";
	FILE* pf = fopen(file, "r");
	if (pf == NULL)
	{
		perror("fopen");
		return;
	}

	int* kminheap = (int*)malloc(sizeof(int) * 10);
	//先从文件中读取最前面的十个元素并且建立小堆
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &kminheap[i]);
		AdjustUp(kminheap, i+1);
	}
	int val = 0;
	while (!feof(pf))//读到文件尾返回非0，读到数据返回0
	{
		fscanf(pf, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}

	//打印堆中元素
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

6. 再次运行，因为刚才已经生成了数据并且我们修改了5个数据，如果再调用CreatNData()就会重新生成一万个数据覆盖掉原来的

好了，已经找到最大的前五个数据

如果想找最小的数据，那就建立大堆，随之，向上向下调整的代码只需更改判断父亲和孩子间大小的符号就行

时间复杂度计算·

时间复杂度计算，按照最坏的情况，那么就是，每个数与堆顶元素比较时都比堆顶元素大，因此需要交换，需要向下调整，那么最坏的情况就是每次要调整到最下层，现在堆中有5个数，3层，所以要调整两次，现在一共有N个数，大概就要调整N*2次，最大调整次数与层数有关，层数又与堆的节点数有关，层对应了节点的范围，h层对应节点数k的范围是[2^(h-2)+1,2^(h-1)]，而调整次数是h-1，因此调整次数与节点数k有了初步地关系，调整次数==logk，一个数据调整一次是logk，所有数据调整的次数就为N*logk