TopK问题

从海量数据中找到 top K个数据

分析：

数据量很大的情况下，要找到最小/大的K条数据，通常使用堆排序，求最小的K个数，用大顶堆，求最大的K个数，用小顶堆

如果数据量很大， 不能一次读入内存，可对原始数据进行分组，获得每组数据的 top K，然后合并筛选后的数据，再找 topK

寻找最小的K个元素的算法：

void HeapAdjust(int* a,int s,int len)
{
	int temp=a[s];
	int j;
	for(j=2*s;j<=len;j*=2)
	{
		if(j<len && a[j]<a[j+1])
			j++;
		if(a[j]<=temp)
			break;
		a[s]=a[j]; s=j;
	}
	a[s]=temp;
}
int * topK(int nums[],int len,int k)
{
	if(k>=len) return nums;
	int* res=new int[k];
	for(int i=0;i<k;i++)
		res[i]=nums[i];
	//初始化大顶堆
	for(int i=(k-1)/2;i>=0;i--)
		HeapAdjust(res,i,k-1);
	// 获得topK
	for(int i=k;i<len;i++)
	{
		if(nums[i]<res[0])
		{
			res[0]=nums[i];
			HeapAdjust(res,0,k-1);
		}
	}
	return res;
}

寻找最大的K个元素的算法：

void HeapAdjust(int* a,int s,int len)
{
	int temp=a[s];
	int j;
	for(j=2*s;j<=len;j*=2)
	{
		if(j<len && a[j]>a[j+1])
			j++;
		if(a[j]>=temp)
			break;
		a[s]=a[j]; s=j;
	}
	a[s]=temp;
}
int * topK(int nums[],int len,int k) //len为原数组长度
{
	if(k>=len) return nums;
	int* res=new int[k];
	for(int i=0;i<k;i++)
		res[i]=nums[i];
	//初始化小顶堆
	for(int i=(k-1)/2;i>=0;i--)
		HeapAdjust(res,i,k-1);
	// 获得topK
	for(int i=k;i<len;i++)
	{
		if(nums[i]>res[0])
		{
			res[0]=nums[i];
			HeapAdjust(res,0,k-1);
		}
	}
	return res;
}