什么是Top-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
在生活中的运用
如果只是数据比较少的，我们可以排序找到前几的数据，但是实际应用中我们时常都会面对海量的数据，大到内存无法全部加载，这就需要我们用数据结构中的堆来解决
基本思路
用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
时间复杂度的计算
然后要遍历数据,最坏的情况是每个元素都与堆顶比较并排序，需要堆化n次
每次最差都下调高度次，而高度为log（k），所以是O(nlog(k))
因此总复杂度是O(k+nlog(k))，也就是O(nlogk)
代码的实现
#include<stdio.h> #include<stdlib.h> void swap(int* a, int* b) { int tem = *a; *a = *b; *b = tem; } void AdjustDown(int* arr ,int n, int location) //在location位置向下调整 { int child = location * 2 + 1; while (child < n) { if (child + 1 < n && arr[child] > arr[child + 1]) { child++; } if (arr[child] < arr[location]) //小堆 { swap(&arr[child], &arr[location]); location = child; child = location * 2 + 1; } else break; } } int* TopK(int* arr, int k,int n) { int* brr = (int*)malloc(sizeof(int) * k); for (int i = 0; i < k; i++)//先建堆 { brr[i] = arr[i]; } for (int i = (k-2)/2; i >=0; i--) { AdjustDown(brr, k, i); } for (int i = k; i < n; i++) { if (arr[i] > brr[0]) { brr[0] = arr[i]; AdjustDown(brr, k, 0); } } return brr; } int main() { int arr[] = { 1,23,2,434,6,567,68,9 }; int n = sizeof(arr) / sizeof(int); int k = 3; int* brr = TopK(arr, k,n); for (int i = 0; i < k; i++) { printf("%d ", brr[i]); } return 0; }
测试结果：
需要注意的是输出的结果并未排好序
只是按堆的形式排好了
