💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
TOP-K问题
一、题目描述
假设有一亿个数据，内存存储不下，而我们只需要这一亿个数据中最大的前K个。
二、 思路：
1.：存前K个数据入堆
从第二个开始，每存储一个数据进来，就对其进行向上调整，使其一直保持为小堆。直到k-1个节点停止存储。
2.再从第K+1个数据开始读取
此时读取的数据就不再往堆中插入了，而是与堆顶元素进行比较，如果比堆顶大，那么就替换堆顶元素，然后进行基于小堆的向下调整。
3.所有数据读取完毕，堆中剩余的K个就是最大的K个数据
三、代码实现
1.随机产生一万个数据，存入文件中。
void CreateNDate() { // 造数据 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); }
2.找前K个最大值
void PrintTopK(const char* filename, int k) { 建堆/用a中前k个元素建堆 FILE* fout = fopen(filename, "r"); if (fout == NULL) { perror("fopen fail"); return; } 开辟K个元素空间 int* minheap = (int*)malloc(sizeof(int) * k); if (minheap == NULL) { perror("malloc fail"); return; } 将前k个元素读入数组minheap for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minheap[i]); } 用前k个数建小堆，使用从下到上的向下调整方法建堆。 k-1下标的双亲节点是（k-1-1）/2； for (int i = (k - 2) / 2; i >= 0; --i) { AdjustDown(minheap, k, i); } 将剩余n-k个元素依次与堆顶元素交换，不满足，则替换 int x = 0; while (fscanf(fout, "%d", &x) != EOF) { if (x > minheap[0]) { 替换堆顶元素进堆 minheap[0] = x; 并且进行调整 AdjustDown(minheap, k, 0); } } 遍历完所有n个数据后，打印出堆中的数据，就是最大的K个数据啦！ for (int i = 0; i < k; i++) { printf("%d ", minheap[i]); } printf("\n"); fclose(fout); } // fprintf fscanf
3.测试类：
int main() { //CreateNDate(); PrintTopK("data.txt", 5); return 0; }
四、时间复杂度和空间复杂度分析
🔸时间复杂度：O(N*logK);
N:节点个数。K：最大的前K个个数
如果N>>K，那么可以认为时间复杂度是O(N);这也是此算法的厉害之处。
🔸空间复杂度：O(K);
K：最大的前K个个数.
