什么是TOPK问题？
📝TOP-K问题：在数据量比较大的情况下求数据集合中前K个最大的元素或者最小的元素，
比如：世界500强的企业、世界富豪榜、游戏中前100的氪金玩家等。
TOPK问题的必要性和详细思路
N个数寻找最大的前k个。
正常思路是把这N个数建成堆，然后 pop k次，即可找到最大的前k个值。
但是有些场景，上面的思路解决不了，比如N非常大的情况。
假设N是10亿，k是100，就不可能运行出结果。
因为如果这样建成堆的话，所占用的空间太大了。
10亿个整数需要多大的空间？答案是4GB。
4GB的内存啥电脑来了也吃不消，再说100亿，1000亿呢？
可见这不是一个可行的方法，咱们另辟蹊径。
我们知道，当数据很大时，它不会存在内存上，而是转而储存在磁盘文件里，所以我们的思路就转向磁盘文件。
磁盘中能建堆吗？答案是不能，因为磁盘不能随机访问。
解决思路，前K个数建小堆，让其它N-K个数和堆顶比较，如果比它大就替换它进堆。
替换它进堆的意思就是，将堆顶元素替换，然后将其向下调整。
最后这个小堆的内容就是最大的前K个。
向下调整算法我上篇文章介绍过，大家不了解的可以看看。
【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法
考虑到要排序的数据可能很多，我们建立一个TXT文件来存放待排序数据。
为了创建足够多的随机数，我们使用srand函数。
void CreateNDate() { // 造数据 int n = 1000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (size_t i = 0; i < n; ++i) { int x = rand() % 10000; fprintf(fin, "%d\n", x); } fclose(fin); }
关于文件的操作，大家有忘记的可以看我之前的文章。
写程序必会的C语言文件操作（上）附手绘图详解
运行代码。
上面我们创建了一个data文件，并且往里面存入了1000个随机数。
用上面的思路将其排序。
首先是建堆，用a中前k个元素建小堆。
然后将剩余n-k个元素依次与堆顶元素交换，不满则则替换。
替换元素之后不要忘记向下调整。
void PrintTopK(int k) { // 1. 建堆--用a中前k个元素建小堆 int* topk = (int*)malloc(sizeof(int) * k); assert(topk); const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen error"); return; } // 读出前k个数据建小堆 for (int i = 0; i < k; ++i) { fscanf(fout, "%d", &topk[i]); } for (int i = (k - 2) / 2; i >= 0; --i) { AdjustDown(topk, k, i); } // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 int val = 0; int ret = fscanf(fout, "%d", &val); while (ret != EOF) { if (val > topk[0]) { topk[0] = val; AdjustDown(topk, k, 0); } ret = fscanf(fout, "%d", &val); } for (int i = 0; i < k; i++) { printf("%d ", topk[i]); } printf("\n"); free(topk); fclose(fout); }
我们人工在data文件里面建立几个大数，运行代码。
成功打印出我们添加的几个大数，排序成功 。
包含TOPK算法的堆的源代码
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> #include<time.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; void AdjustUp(HPDataType* a, int child); void AdjustDown(HPDataType* a, int n, int parent); void HeapInit(HP* php); void HeapDestroy(HP* php); void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); HPDataType HeapTop(HP* php); bool HeapEmpty(HP* php); //int HeapSize(HP* php); void Swap(HPDataType* p1, HPDataType* p2); void HeapSort(int* a, int n); void HeapDestroy(HP* php); void CreateNDate(); void PrintTopK(int k); #define _CRT_SECURE_NO_WARNINGS #include"heap.h" void HeapInit(HP* php) { assert(php); php->a = NULL; php->size = 0; php->capacity = 0; } void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->capacity = 0; } void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child+1< n && 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 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; } } } bool HeapEmpty(HP* php) { assert(php); return php->size == 0; } void HeapPush(HP* php, HPDataType x) { assert(php); if (php->size == php->capacity) { int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType)); if (tmp == NULL) { perror("realloc fail"); return; } php->a = tmp; php->capacity = newCapacity; } php->a[php->size] = x; php->size++; AdjustUp(php->a, php->size - 1); } void HeapPop(HP* php) { assert(php); Swap(&php->a[0], &php->a[php->size - 1]); php->size--; AdjustDown(php->a, php->size,0); } HPDataType HeapTop(HP* php) { assert(php); return php->a[0]; } //void HeapSort(int* a, int n) //{ // HP hp; // HeapInit(&hp); // for (int i = 0; i < n; i++) // { // HeapPush(&hp, a[i]); // } // int i = 0; // while (!HeapEmpty(&hp)) // { // int top = HeapTop(&hp); // a[i++] = top; // HeapPop(&hp); // } // HeapDestroy(&hp); //} //换出我们想要的结构，向上建立小堆，然后删除元素，最后建立大堆 1 3 5 4 5 9 7 8 //建小队回损坏结构 //向下调整算法可以帮我们完成工作 //升序-》建大堆 降序-》建小堆 void HeapSort(int* a, int n) { int end = n-1; //向上调整建堆 for (int i = 1; i < n; i++) { AdjustUp(a, i); } //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } while (end>0) { Swap(&a[0], &a[end]); AdjustDown(a,end, 0); --end; } } void CreateNDate() { // 造数据 int n = 1000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (size_t i = 0; i < n; ++i) { int x = rand() % 10000; fprintf(fin, "%d\n", x); } fclose(fin); } void PrintTopK(int k) { // 1. 建堆--用a中前k个元素建小堆 int* topk = (int*)malloc(sizeof(int) * k); assert(topk); const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen error"); return; } // 读出前k个数据建小堆 for (int i = 0; i < k; ++i) { fscanf(fout, "%d", &topk[i]); } for (int i = (k - 2) / 2; i >= 0; --i) { AdjustDown(topk, k, i); } // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 int val = 0; int ret = fscanf(fout, "%d", &val); while (ret!=EOF) { if (val > topk[0]) { topk[0] = val; AdjustDown(topk, k, 0); } ret = fscanf(fout, "%d", &val); } for (int i = 0; i < k; i++) { printf("%d ", topk[i]); } printf("\n"); free(topk); fclose(fout); } //test.c #define _CRT_SECURE_NO_WARNINGS #include"heap.h" void UpSort(HPDataType* a, int n) { for (int i = 1; i < n; i++) { AdjustUp(a, i); } } int main() { HP hp; HeapInit(&hp); int a[] = { 7,8,4,6,3,0,1,2,5,9 }; //HeapSort(a, sizeof(a) / sizeof(a[0])); int n = sizeof(a) / sizeof(int); HeapSort(a, sizeof(a) / sizeof(a[0])); /*for (int i = 0; i < sizeof(a) / sizeof(int); ++i) { HeapPush(&hp, a[i]); } while (!HeapEmpty(&hp)) { printf("%d\n", HeapTop(&hp)); HeapPop(&hp); }*/ for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { printf("%d ", a[i]); } printf("\n"); //CreateNDate(); PrintTopK(5); return 0; }
TOPK算法复杂度分析
一开始需要对K个元素进行建堆，时间复杂度为O(k)，之后遍历数组,最坏的情况是，每个元素都与堆顶比较并排序，需要调整n次 复杂度是O(nlog(k))，因此总复杂度是O(k+nlog(k));
如有错误欢迎大佬评论区指正。
欢迎转载，烦请署名并保留原文链接。
