C语言描述数据结构 —— 二叉树(2)Top-K问题

1.前言

Top-K问题在生活当中是非常常见的，例如各个板块的排行榜、电商平台的产品热度排名、价格排序……这些例子统统围绕一个核心：从N个数据中找出k个最大、最小、最热等的数据。我们可以使用堆来解决Top-K问题，即求数据中前k个最大或最小的元素，当然处理的数据量也非常庞大。其实在处理一般数据的时候，我们想到的一般方法是对数据进行排序，排序就意味着数据是有序的，有序的就可以很简单的选出前k个符合条件的数，但是数据量一旦大了起来，排序就显得不合适了。

2.使用堆解决Top-K问题

当我们要使用堆来处理数据的时候，就必然会涉及建堆的问题，那么建堆的核心点就在于，我们要建一个多大的堆，是大堆还是小堆。我们在实现堆这个数据结构的时候，实现了一个HeapPop接口，删除堆中堆顶的元素，删除的逻辑相信大家也能够理解，即可以找到次大或次小的数，但是这样做是得不偿失的，首先如果数据量很大，那么空间就是一个问题，因为我们要建一个非常大的堆，其次就是每次删除之后要重新建堆，那么时间复杂度就上去了，所以这并不是一个好的解决方案。 

总上所述，我们得出结论：

• 找前k个最小的数，建小堆不可取
• 找钱k个最大的数，建大堆不可取

如果我们反其道而行之，找前k个最小的数，建大堆可以吗？找前k个最大的数，建大堆可以吗？我们介绍一种算法。

可以看到，我们的空间复杂度、时间复杂度都降下去了，而且算法效率也非常的高。只不过需要注意一点，最后的结果不一定是有序的，但它一定是符合条件的。 所以我们得出结论：

• 找前k个最大的数据，建小堆
• 找前k个最小的数据，建大堆

现在就可以将思路转换成代码了，不过在这里呢，我们使用文件的方式来存储数据，这就在一定程度上模拟了很多排序算法。

#include  
#include 
#include 
 
//文件中写入随机数
void CreateData(const char* filename, int N)
{
	assert(filename);
	FILE* fin = fopen(filename, "w");
	assert(fin);
	srand((unsigned int)time(NULL));
	for (int i = 0; i < N; i++)
	{
		fprintf(fin, "%d\n", rand());
	}
	fclose(fin);
}
//交换
void Swap(int* p1, int* p2)
{
	assert(p1 && p2);
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向下调整
void AdjustDown(int* ph, int n, int parent)
{
	assert(ph);
	int minchild = parent * 2 + 1;
	while (minchild < n)
	{
		if (minchild + 1 < n && ph[minchild + 1] < ph[minchild])
		{
			minchild++;
		}
		if (ph[minchild] < ph[parent])
		{
			Swap(&ph[minchild], &ph[parent]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void PrintTopK(const char* filename, int K)
{
	assert(filename);
	//建立文件
	FILE* fout = fopen(filename, "r");
	assert(fout);
	//把前k个元素放入堆中
	int* minHeap = (int*)malloc(sizeof(int) * K);
	assert(minHeap);
	for (int i = 0; i < K; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//找前k个最大的数据，建小堆
	for (int i = (K-2)/2; i>=0; i--)
	{
		AdjustDown(minHeap, K, i);
	}
	
	//堆顶元素与剩下的元素比较
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			AdjustDown(minHeap, K, 0);
		}
	}
 
	//打印
	for (int i = 0; i < K; i++)
	{
		printf("%d ", minHeap[i]);
	}
	//关闭文件
	fclose(fout);
}
int main()
{
	int N = 10000;
	int K = 10;
	const char* filename = "Data.txt";
	//CreateData(filename, N);
	PrintTopK(filename,K);
	return 0;
}

如果我们对打印的结果有问题的话，我们还可以去文件中随机加几个值：

 如果大家想完成前k个最小的数，可以尝试建大堆，并改变一下堆顶元素的比较的条件。