[C/C++]用堆实现TopK算法
一:引入
思考一个问题: 怎么在100个数中找到前10个最大的数?
way1: 相信大多数人想到的方法是先把100个数放到数组中从大到小排序,再打印前10个数
way2: 前一文中我们讲了堆结构,那么就可以把这100个数建为大堆,再依次pop10次
这种方法虽然再这个问题下可行,但是如果是再1亿个数中找最大的十个数呢?
当数据多到内存都放不下时这种方法显然不可取
二:TopK问题
TopK问题就是说在N个数据中找到前k个最大或最小的数(前提是N远大于k)
解决方法:
我们以找到前k个最大的数为例
- 将数据前k个数建成一个小堆
- 从第k+1个元素开始遍历数据,如果比堆顶元素大的话就交换
- 交换完以后,将堆顶元素向下调整到合适位置
- 依次反复遍历所有元素即可
为什么要建立小堆而不建大堆呢?
因为如果建大堆,如果数据中最大的元素堵在堆顶,那剩下的k-1大的元素就进不了堆了,相反如果建立小堆,大的数据会往下沉,堆顶的元素是堆里面最小的元素,只要后面的数据比堆顶大就可以交换入堆,这样遍历完一遍数据后,最大的k个数就全部在堆里面了
模拟验证:
在文件中创建10万个随机数,找前10个最大的数
1.先创建随机数
由于rand创建的随机数只有三万多个,而我们需要10万个,这样就会有许多重复的数据,加i是为了让重复的数据减少,取模100000是为了将随机数控制在100000以内
void creatnum()
{srand(time(0));int n = 100000;FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 100000; //由于rand最多只能产生三万多个随机数,加i可以让重复的数字大幅减小fprintf(fin,"%d\n",x);}fclose(fin);
}2.打印前5个最大的数据(TopK问题精髓) 重点重点!!
对于向上调整法和向下调整法,可以看[C/C++]数据结构 堆的详解
void printTopk(const char* file,int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen");return;}//创建一个小堆(找最大数创小堆,找最小数创大堆)int* heap = (HeapDataType*)malloc(sizeof(HeapDataType) * k);if (heap == NULL){perror("malloc");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &heap[i]);AdjustUp(heap, i);}//读数据,如果比堆头的数大就交换,再向下调整int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > heap[0]){heap[0] = x;AdjustDown(heap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", heap[i]);}printf("\n");free(heap);fclose(fout);
}3.测试代码
int main()
{creatnum();//printTopk("data.txt", 5);return 0;
}由于10万个数都是随机产生的,所以我们无法验证打印的数是不是正确的,但是我们直到这十万个数都是小于100000的,所以我们先调用创建随机数的函数,然后我们在打开文件,改五个大于100000的数,看打印结果是不是我们改的数即可.
ps:在修改完数据后,准备打印数据之前,一定要把创建随机数的函数注释掉,因为再次调用的话,我们是以'w'的方式打开文件的,如果文件存在的话数据会被清空重新产升随机数,这样我们改的数据就不存在了
