TOP-K介绍

什么是TOP-K？贴近生活来说，点外卖，打游戏。比如某团，你点一个美食，选你选在城市后，你选择按评分排序，那么它会将这个城市里所有美食店铺评分最高的依次排列；再准确点，再比如游戏内的国标，国标就是总体数据，去排一个国家内前100熟练度最高的玩家，再给前100的玩家颁发国标

这就是TOP-K问题在一个大数据中（这个大数据通常非常大，我们在这个大数据中选取前10，前100的数据。

TOP-K实现思路

那么我们用的方法是用堆来实现，

1.先建一个仓库，这个仓库是按从小到大的顺序来排的，仓库最上方最小的（叫做仓顶）

2.我们去遍历这个大数据，如果大数据中有比这个仓顶大的，那么我们就把大数据中这个数放入仓顶。

3.放入后，我们重新排列仓库，永远保存仓库是从小到大的顺序来排的，仓顶永远是仓库中最小的数字

4.等我们遍历完这个大数据，那么仓库中就是大数据中前K个最大的数

那么我们把仓库换成堆试试

比如仓库的从小到大的顺序，就比作小堆，小堆的堆顶就是堆中最小的数。

那么思路有了，就可以思路转代码了

TOP-K实现

首先我们定义出这个大数据中有多少个数，然后申请出这个空间，利用随机数，再这个空间中放慢随机值，

（因为我们需要准确性，所以特意在数据中一些地方放入较大的值，如果结果是这些较大的值，那么说明我们排序成功）

这时候就开始实现TOP-K

按照前面的思路，我们先申请出一个空间，即仓库（堆）

把大数据中前K个值放入堆中（这里大数据的值都是随机的）

然后建小堆

依次去遍历大数据跟堆顶比较，如果大于，就放入堆，并且重新建堆，让堆顶保持是堆中最小

（依次反复，大数据中前K个大的数全在堆中）

最后我们打印堆中的数据（数据可能不是有序的，因为是堆，如果你想要有序，可以对堆进行排序）

源码

void TopK(int* a, int size, int k)
{int* TopKsort = (int*)malloc(sizeof(int)*k);for (int i = 0; i < k; i++){TopKsort[i] = a[i];}//建K的小堆for (int i = (k-1-1)/2; i>=0; --i){ADjustDown(TopKsort, k, i);}//依次遍历Size-K个数 如果比K大就入堆for (int i = k; i < size; i++){if (a[i] > TopKsort[0]){TopKsort[0] = a[i];ADjustDown(TopKsort, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", TopKsort[i]);}
}
int main()
{int n = 10000;int* a = (int*)malloc(sizeof(int)*n);srand(time(0));for (size_t i = 0; i < n; i++){a[i] = rand() % 1000000;}a[4342] = 1000000 + 1;a[4343] = 1000000 + 9;a[4354] = 1000000 + 2;a[4339] = 1000000 + 4;a[436] = 1000000 + 3;a[4332] = 1000000 + 5;a[4330] = 1000000 + 7;a[4337] = 1000000 + 6;a[4336] = 1000000 + 10;a[43] = 1000000 + 8;TopK(a, n, 10);return 0;
}