【TopK问题】——用堆实现

文章目录

• 一、TopK问题是什么
• 二、解决方法
• 三、时间复杂度

一、TopK问题是什么

TopK问题就是从1000个数中找出前K个最大的数或者最小的数这样的类似问题。

不过并不要求这k个数字必须是有序的，如果题目有要求，则进行堆排序即可。

还有比如求出全国玩韩信前十名等等，排出班级前十名也是TopK问题。

二、解决方法

采用堆的方式可以较快解决。

思路：如果需要排前k个最大的数，则需要建一个小堆
如果需要排前k个最小的数，则需要建一个大堆

假设现在需要排序前k个最大的数，则需要建立一个小堆。
建立小堆是拿n个数的前k个数来建立的。

不能把n个数全部建立成一个小堆，这样效率会大打折扣，因为通过向下调整建堆的时间复杂度是O(N)，假如要从10亿个数字中排前50个最大的，那么建立一个10亿个数大小的堆，开销还是比较大的。

建立了一个小堆后，此时堆顶元素是最小的，
从第k+1个数开始，只要第K+1个数大于堆顶元素，就将该数字于堆顶元素进行交换，然后再向下调整。

这样做的结果是：只要我比堆顶元素大，我就进堆，如果我在堆中是比较大的，我就会“下沉”到堆底，（因为这是一个小堆）。
这样遍历多次后，原来堆中的元素会被换成新的一批更大一点的元素。

当我们遍历完n个数后，留在堆中的一定是前k个最大的数。

代码如下：
随机生成10个1000以内的数字，求这10个数字的最大的3个：

void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设左孩子就是最大的
	int child = (parent * 2) + 1;
	while (child < n)
	{
		//筛选左右孩子谁大
//		if(a[child+1]>a[child]),不能这样判断
		//(因为有可能存在右孩子不存在的情况，需要判断一下右孩子是否存在)
		//否则容易出现越界问题
//		if (a[child + 1] > a[child] && child + 1 < 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 Find_TopK(int* a, int n ,int k)
{
	assert(a!=NULL);
	assert(k > 0);

	int* topk = (int*)malloc(sizeof(int) * k);
	assert(topk);
	for (int i = 0; i < k; ++i)
	{
		topk[i] = a[i];
	}

	//1.先建堆,向下调整建堆，现在是建小堆，那就找最大的前k个
	//把前k个抓起来，建立一个k大小的堆

	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(topk, k, i);
	}

	//2.然后从第k个开始，往堆里面插入
	int j = k;
	while (j < n)
	{
		if (a[j] > topk[0])
		{
			topk[0] = a[j];
			AdjustDown(topk, k, 0);
		}
		j++;
	}

	printf("这10个数中最大的3个数为：\n");
	for (int i = 0; i < k; ++i)
	{
		printf("%d ", topk[i]);
	}

	free(topk);
	topk = NULL;
}

int main()
{
	srand(time(0));
	int a[100] = { 0 };
	printf("随机生成的10个1000以内的数为：\n");
	for (int i = 0; i < 10; ++i)
	{
		a[i] = rand() % 1000;
		printf("%d ", a[i]);
	}
	printf("\n");
	int k = 3;

	int n = sizeof(a) / sizeof(a[0]);
	Find_TopK(a,n,k);
	return 0;
}

三、时间复杂度

建堆的时间复杂度:O(K)
遍历的时间复杂度:O(N-K)
每次遍历调整的时间复杂度:O(logK)
总的时间复杂度O(K+(N-K)logK) ≈ O(NlogK)