经典面试题：TopK问题(一种思路，两种优化，最终优化到极致)

一、问题描述

在面试中面试官经常会问这样一个问题：现在有N个数，请找出最大的或最小的前k个数，这就是经典的TopK问题，这种问题在实际的业务非常的常见，比如微博的热搜排名，抖音的每日热榜排名等等都是属于这种Top问题。

二、解决思路及优化

2.1 排序（快速排序或堆排序）

当我们看到这种题目的时候，大多第一反应都是排序，将这N个数按升序或降序的方式排好序，然后再取前k个最小或最大的数；当然这种思路是没有任何问题的，但问题是选择哪一种排序呢？众所周知，快速排序是排序算法中最时间复杂度相对较优的算法，快速排序的平均时间复杂度是O(N * logN) 。但是本篇将着重使用堆排序进行相应的优化。

堆排序的核心思想：（前提是我们要建好一个相应的堆，这里我们用含N个数的大堆来说） 每次将建好的大堆的最后一个叶子节点和根节点进行互换，然后执行一次向下调整算法调整堆的结构，再将指向堆最后位置的指针减1(相当于将最大的数放在最后一个，并且排除它)。大根堆是所有父亲节点均大于其对应的孩子节点，而我们要求的是升序的堆，大根堆的根节点肯定是堆里最大的数，因此，我们可以通过将根节点和最后一个叶子节点互换，并将最后一个叶子节点的指针减1，即可保存最大的值，但是互换过去的叶子节点破坏了原来大根堆的结构，因此我们就需要用向下调整算法来恢复结构以便于选出次大的数。

堆排序的时间复杂度为O(N * logN)

代码实现

//升序
void HeapSort(int* arr, int n)
{
	//升序要首先建立大堆
	//建堆的时间复杂度为o(N)
	for(int i = ((n - 1) - 1) / 2 ; i >= 0; i--)
	{
		AdjustDown(arr,n,i);	
	}
	//每次选出剩余数中最大的数，并保存到每次最后的节点
	int end = n - 1;
	while(end > 0)
	{
		int tmp = arr[end];
		arr[end] = arr[0];
		arr[0] = tmp;

		//选出次小的数
		//AdjustDown为向下调整算法
		AdjustDown(arr,end,0);
		--end;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

具体思路分析和相应的算法展示，以及堆排序时间复杂度的计算请看：面试考点–堆(向下调整算法，向上调整算法，建堆，堆排序)以及堆排序、建堆的时间复杂度分析(图文并茂)

2.2 优化

2.2.1 第一次优化

当你回答面试官解决此问题可以采用堆排序或快速排序选出前k个数的后，然后面试官可能会提出这样的要求：解决该问题的效率不够，请继续优化。

优化思路：

首先建一个N个数的大堆(小堆)，然后每次将根结点(最大的值)移除，然后重新调堆(向下调整算法)，继续选出次大的值，然后移除，直至选出k个次大的数；

时间复杂度分析：

向下调整算法的时间复杂度为O(logN),要重新调堆k次，因此时间复杂度为O(K * logN)，由于建堆的时间复杂度为O(N)，因此该算法的总的时间复杂度为 O(N + K * logN) ，随着n的增大，O(K * logN)会趋于平缓，但 O(N)是线性增长，因此该算法的时间复杂度趋近于O(N)。

2.2.2 第二次优化

当你采用以上回答时，面试官为了更近一步考验你，可能会这样说：假设当N非常大的时候，比如说总共有10亿个数，内存中放不下这么多的数，数据保存在文件中，采用上面的方法会非常耗费内存空间，请继续进行优化。

优化思路：

首先还是先建一个堆，若是求前k个最大的数(降序)就建大堆，反之(升序)建小堆，但此次建堆只建k个数的堆(之前是建N个数的堆)，然后将剩下N-K个数依次去和堆顶的数(根节点)进行比较，如果要比堆顶的数大，则替换堆顶的数，再进行向下调整算法，然后循环依次进行比较，最终，最大的前k个数，就在该堆里面；

时间复杂度分析：

首先，建立k个数的堆的时间复杂度为O(K)，然后假设在最坏的情况下，需要比较N-K次，也就是说需要进行N-K次向下调整算法，因此，调堆的时间复杂度为O((N-K) * logK)；则总的时间复杂度为O(K + (N-K) * logK)，由于K是定值，并且现实业务中，往往都是N的值非常的大，然后K的值非常的小，(拿微博热搜来说就是要在全国几亿条新闻中，选出十几或二十几访问量最多的新闻作为热搜)，所以，该算法的时间复杂度趋近于O(N)。

代码实现

/* 堆的结构
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity; 
}Heap;
*/

//找最大的K个元素
//假设堆为小堆
void PrintTopK(int* a, int n, int k)
{
    Heap hp;
    //建立含有K个元素的堆
	HeapInit(&hp, a, k);
 
    for (int i = k; i < n; ++i)  // N
	{
        //每次和堆顶元素比较，大于堆顶元素，则删除堆顶元素，插入新的元素
		if (a[i] > HeapTop(&hp)) // LogK
		{
			HeapPop(&hp);
			//在进行插入操作时，会进行调整
			HeapPush(&hp, a[i]);
		}
	}
	
    for(int i = 0; i < k; ++i){
        printf("%d ",HeapTop(&hp));
        HeapPop(&hp);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

到此为止，才是最终的既节省内存空间，效率又相对较高的解决TopK问题的解决方案