【数据结构】TopK问题_前k大的数

TopK

在N个数中 找出最大或最小的前k个数，就是TopK算法。比如有一组数字，[1,2,3,4,5,6,7,8,9]，这组数中最大的前 3(k)个数是 9,8,7。最小的 前3个数是 1，2，3。而TopK算法就是找出最大或者最小的前K个数。我们就用堆来实现。

之前讲解过如何写一个堆，博客链接 ，代码git链接。
今天我们就用这个堆，来实现TopK算法。

找到前k个最大的数的方法有很多，我们可以取堆顶，然后在pop掉堆顶，Pop K次，如果是大堆，那么就是前K个最大的数。如果是小堆，那么就是前K个最小的数。 但再此之前我们要先把 数据依次 Push到堆中，但这个方式有一个弊端，如果数据很多，有1亿个，是从文件中读取的话。那么要把1亿个数全都读到内存，但是内存的的空间是有限的，放不下如此多的数据，所以这个方法就不可行了，今天就给大家介绍一种更方便的方法。

算法思路

我们可以构建一个 有K个数的小堆，依次Push。
比如上面举的例子，1-9，找出最大的前3个数。
那么此时，K = 3， 找最大的前3个数，我们就构建小堆。
我们随机取3个数，2，6，9，放入小堆中。

随后我们拿剩下 N - K个数与堆顶进行比较，如果比堆顶大，那么就用这个数替换堆顶，随后进行向下调整。

第一次比较

第二次比较

第三次比较

上面三次都没有发生向下调整，因为堆顶的元素比它的两个孩子小，但下一次比较会发生向下调整！

第四次比较

向下调整后，我们就发现，堆顶元素变成了 5。

第五次比较和第四次比较一样，会发生向下调整。
第五次比较

第6次比较

比较完之后，我们会发现我们的堆是这样的

我们可以发现，7，8，9 就是我们 1 - 9 中 最大的前3个数。

代码实现

那么代码我们就可以这样写。

void PrintTopK(int* data, int len, int k)
{
   
	//建立一个堆
	HP hp;
	HeapInit(&hp);
	//插入K个数据
	for (int i = 0; i < k; i++)
	{
   
		HeapPush(&hp, data[i]);
	}
	//随后进行比较，是否比栈顶元素大
	for (int i = k; i < len; i++)
	{
   
		
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18