TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
就是从N个数里面找最大前K个（N远大于K）
思路一：
- N个数插入到堆里面，PopK次
时间复杂度是
O(N*logN) + K*logN==O(N*logN)
- N很大很大，假设N是100亿，K是10
100亿个整数大概需要40G左右
所以这个思路很不好~~
思路二：
- 读取前K个值，建立K个数的小堆
依次再取后面的值，跟堆顶比较，如果比堆顶大，替换堆顶进堆（替换对顶值，再向下调整）
时间复杂度是O(N*logK)
随机生成一些数据，找前k个最大值
- 那么我们就先要造数据，随机生成
void CreateData() { //造数据 int n = 100000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; i++) { int x = (rand() + i) % 100000; fprintf(fin, "%d\n", x); } fclose(fin); }
- 打开项目的源文件所在的文件夹，就会有这个data.txt的文件，里面已经随机生成了10万个数字
进行取前k个值建堆
- 我们先从文件中读数据
- 然后取前k个进行建立一个小堆
- 读取前k个数，边读边建立小堆
- 如果读取的整数 x 大于堆顶元素，将堆顶元素替换为 x，然后进行向下调整
void PrintTopK(const char* file, int k) { //读文件 FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen error"); return; } //建立一个k个数的小堆 int* minheap = (int*)malloc(sizeof(int) * k); if (minheap == NULL) { perror("malloc error"); return; } //读取前k个数 //边读边建小堆 /*for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minheap[i]); AdjustUp(minheap, i); }*/ // 建小堆 for (int i = (k-1-1)/2; i >= 0; i--) { AdjustDown(minheap, k, i); } //读取剩余的值，读到x里 int x = 0; while (fscanf(fout, "%d", &x) != EOF) { 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); }
找到了前k个结果以及全部代码
- 比如我取前5个最大的，我们来看一下结果
void AdjustUp(HPDataType* a, int child) { 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(HPDataType* a, int size, int parent) { 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 CreateData() { //造数据 int n = 100000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; i++) { int x = (rand() + i) % 100000; fprintf(fin, "%d\n", x); } fclose(fin); } void PrintTopK(const char* file, int k) { //读文件 FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen error"); return; } //建立一个k个数的小堆 int* minheap = (int*)malloc(sizeof(int) * k); if (minheap == NULL) { perror("malloc error"); return; } //读取前k个数 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minheap[i]); //向上调整 AdjustUp(minheap, i); } //边读边建小堆 //读取剩余的值，读到x里 int x = 0; while (fscanf(fout, "%d", &x) != EOF) { //如果堆里的元素小于x就继续调整 if (minheap[0] < x) { //将x搞到堆顶 minheap[0] = x; //向下调整 AdjustDown(minheap, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", minheap[i]); } free(minheap); fclose(fout); } int main() { //CreateData(); PrintTopK("data.txt",5); return 0; }
- 那么我们知道这前5个是最大的吗？
- 这个时候就要加入我们的密探，手动从文件里加入5个最大的数~~
- 加入这几个数
100001100002100003100005100004 - 然后再执行代码，可以看到已经完美的出来了~~
