【数据结构】堆的TopK问题

大家好，我是苏貝，本篇博客带大家了解堆的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;}elsebreak;}
}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;
}

---

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