Top - k问题

什么是Top - k问题？

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。

最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆前k个最大的元素，则建小堆，前k个最小的元素，则建大堆

2.  用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。

代码实现如下：

//用堆来解决topk问题 
void PrintTopK(int* a, int n, int k)
{
	int i,j;
 // 1. 建堆--用a中前k个元素建堆
   int parent=(k-1)/2;
   for(i=parent;i>=0;i--){
		
		AdjustDown(a,i,k);
	}
 // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
    for(i=k+1;i<n;i++){
    	if(a[i]>a[0]){
    		swap(a,0,i);
    		AdjustDown(a,0,k);
		}
	}
	for(i=0;i<k;i++){
		printf("%d ",a[i]);
	}
}
void TestTopk()
{
 int n = 10000;
 int* a = (int*)malloc(sizeof(int)*n);
 srand(time(NULL));
 for (size_t i = 0; i < n; ++i)
 {
   a[i] = rand() % 1000000;
 }
 a[5] = 1000000 + 1;
 a[1231] = 1000000 + 2;
 a[531] = 1000000 + 3;
 a[5121] = 1000000 + 4;
 a[115] = 1000000 + 5;
 a[2335] = 1000000 + 6;
 a[9999] = 1000000 + 7;
 a[76] = 1000000 + 8;
 a[423] = 1000000 + 9;
 a[3144] = 1000000 + 10;
 PrintTopK(a, n, 10);
}

最终得到我们要的数：