问题描述
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
- 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
算法思路
大致的实现代码是这样
数据量非常非常大的时候，比如在文件中有1000000000个值，找出最大的前十个
这时我们不可能建大堆去pop 10次，太消耗内存了
我们的思路是：假如TopK
- 创建数据到文件中
- 读取文件前k个值，构建一个k个数的小堆
- 读取文件剩下的值，与堆顶的数比较，如果比堆顶数值大，那就替换他，并向下调整
- 打印前k个数据
1.创建数据到文件中
这里我们创建数据的时候%了10000000，保证数据都是在10000000以内的
我们创建的文件就在文件夹中
2.并构建一个k个数的小堆
3.读取文件剩下的值
总代码
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <time.h> void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = *p1; } void AdjustUp(int* 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(int* 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 CreatNDate() { //造数据 int n = 10000000; 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) % 10000000; 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 fail"); return; } //读取前k个数 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minheap[i]); //建小堆 AdjustUp(minheap, i); } //读文件剩下的值 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]); } printf("\n"); fclose(fout); } int main() { //CreatNDate(); PrintTopK("data.txt", 5); return 0; }
结果我们就可以找出前k个值了
