【数据结构】堆的TopK问题
大家好，���是苏貝，本篇博客带大家了解堆的TopK问题，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️
目录
- 一. 前言
- 二. TopK
- 三. 代码
一. 前言
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决
二. TopK
思路:
- 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
- 用剩余的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在上面代码的操作下，我们能保证所有的随机值都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]3
要找出最大的k个值时，为什么不用大堆？
因为如果最大值先出来，就占据了堆顶的位置，此时次大值就因为 // assert(a); // // int child = parent * 2 + 1; // while (child
三. 代码
#include #include #include #include //构建数据 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 0) { if (a[child] minheap[0]) { minheap[0] = x; AdjustDown(minheap, k, 0); } } for (int i = 0; i好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞👍吗，感谢看到这里，我们下篇博客见❤️
- 用数据集合中前K个元素来建堆