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

问题导入：

假使有一亿个整数要去排序，从中找出k个最大值和k个最小值，当前的内存仅仅可以保留k个整数应当如何存储

内容扩展：

1GB=1024MB=1024*1024KB=1024*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_MAX+1得到[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; }