一亿数据找Top K，内存仅存k个元素（Top—K问题）

问题导入假使有一亿个整数要去排序从中找出k个最大值和k个最小值当前的内存仅仅可以保留k个整数应当如何存储内容扩展1GB1024MB1024*1024KB1024*1024*1024Byte≈10.7亿字节一个整形需要用到4个字节一亿个整形要用到四亿个字节大约是0.3725GB核心思路数据不可以也不被允许放在内存里大多数应该存储在磁盘文件中内存中仅仅只存储维护一个大小为k的堆中求最大的K个数据用小根堆求最小的K个数据用大根堆将文件data.txt放在磁盘中程序采用fscanf或read一个一个读取数据内存中仅仅保留k个候选元素构成一个堆时间复杂度O(nlogk)[n是要处理的总数据量] 空间复杂度O(k)求最大K个元素为何要去建立小根堆step1先读取K个元素建立小根堆step2小根堆的堆顶是这K个元素中最小的step3: 继续遍历剩下n-k个元素如果新元素x堆顶元素说明x比这K个元素里的最小值大将堆顶元素删去换成x而后进行下沉调整保持小根堆同理求取最小的K个元素建立大根堆代码实践文件data.txt写入void CreatFile(void) { FILE* fput fopen(data.txt, w);//以写入的方式创建文件 if (fput NULL) { perror(fopen); return; } // 生成 100000 个 [0, 999999] 的整数 for (int i 0; i 100000; i) { int a (int)((double)rand() / ((double)RAND_MAX 1) * 1000000);//rand()函数的返回值是一个伪随机整数范围在0~RAND_MAX除以RAND_MAX1得到[0,1)的浮点数再乘以1000000并且强制转换为整数 fprintf(fput, %d\n, a);//写入文件 } fclose(fput);//关闭文件 }建立小根堆// 交换两个整数 void swap(int* a, int* b) { int t *a; *a *b; *b t; } // 小根堆向下调整 // arr: 堆数组, n: 堆大小, i: 当前要调整的节点下标 void AdjustDown(int* arr, int n, int i) { while (1) { int l 2 * i 1; int r 2 * i 2; int smallest i; if (l n a[l] a[smallest]) smallest l; if (r n a[r] a[smallest]) smallest r; if (smallest i) break; swap(a[i], a[smallest]); i smallest; } } // 建小根堆 void BuildMinHeap(int a[], int n) { for (int i (n - 2) / 2; i 0; --i) { AdjustDown(a, n, i); } }求最大的K个数并且进行打印// 求最大的 k 个数并打印 void Print_Top_k(int k) { FILE* fout fopen(data.txt, r); if (fout NULL) { perror(fopen); return; } //创建长度为k的数组 int* arr (int*)malloc(sizeof(int) * k); if (arr NULL) { perror(malloc); fclose(fout); return; } // 先读 k 个元素 int n 0; int x; while (n k fscanf(fout, %d, x) 1) { arr[n] x; } //如果没有读取元素那么就退出 if (n 0) { printf(文件没有数据\n); free(arr); fclose(fout); return; } // 如果文件数据不足 k 个就按实际数量处理 k n; // 建成小根堆 BuildMinHeap(arr, k); // 遍历剩余数据 while (fscanf(fout, %d, x) 1) { if (x arr[0]) { // 比堆顶大替换堆顶 arr[0] x; AdjustDown(arr, k, 0); } } //关闭文件 fclose(fout); // 输出堆中元素此时是小根堆结构不保证有序 printf(最大的 %d 个数小根堆结构\n, k); for (int i 0; i k; i) { printf(%d , arr[i]); } printf(\n); //这里采用简单选择排序因为处理的元素个数比较小对k个元素进行完整排序 for (int i 0; i k - 1; i) { for (int j i 1; j k; j) { if (arr[j] arr[i]) { swap(arr[i], arr[j]); } } } //排序后打印 printf(排序后从大到小\n); for (int i 0; i k; i) { printf(%d , arr[i]); } printf(\n); free(arr); arr NULL; }主函数测试int main() { CreatFile(); // 生成 data.txt int k 0; printf(请输入 k); scanf(%d, k); if (k 0) { printf(k 必须大于 0\n); return 1; } Print_Top_k(k); return 0; }