【数据结构初阶】二叉树——堆的应用（堆排序 + TOP-K问题）

上一篇我们讲了二叉树的概念，以及堆的结构和实现。不了解的 点击此处进行了解。

本篇，博主分享的是堆的应用

一、堆排序

概念：

堆排序，即利用堆的特性设计的一种排序算法。堆排序通过建大堆或者建小堆来进行排序的算法

举例：
假如有一个数组a = { 65, 100, 60, 32, 50, 70 } ，从逻辑上我们可以把它看作一个完全二叉树，但不一定是堆，所以我们需要先将数组建成堆，建大堆（或者建小堆）我们就可以再堆顶上选出最大（或最小）的数据，通过不断的选数，我们就可以按照升序或降序将数据排好了。

如何建堆：
再上一篇我们讲过有两种建堆的方式，如下：

1. 向上调整建堆
时间复杂度为O(N*logN)
向上调整建堆：从第二个结点开始向上调整，依次往后。与堆的插入类似。
代码实现如下：

void HeapCreate(HPDataType* a, int size)
{
	assert(a);
	for (int i = 1; i < size; ++i)//从第二个结点开始遍历
	{
		//向上调整建大堆
		AdjustUp(a, i);
	}
}
1
2
3
4
5
6
7
8
9

2. 向下调整建堆
时间复杂度为O(N)

向下调整建堆，从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

代码实现

void HeapCreate(HPDataType* a, int size)
{
	assert(a);
	for (int i = (size - 1 - 1) / 2; i >= 0; --i)//从最后一个叶结点的父结点开始到根结点
	{
		//向下调整建大堆
		AdjustDown(a,size, i);
	}
}

1
2
3
4
5
6
7
8
9
10

当我们将堆建立好之后，接下来，我们要将对已经建好的堆进行排序。这里我们可能就会有个疑惑了？

排升序 – 建大堆还是小堆？
排降序 – 建大堆还是小堆？

可能会有人认为，排升序应该建立小堆，因为小堆的堆顶就是最小的数据，不断的取堆顶元素就可以形成升序。可是如果这样的话，当我们取出堆顶最小的数据后，若想选出次小的数，就要删除首元素，那么剩下的数据就构成不了小堆了，那我们就需要从第二个数据开始又重新建堆，这样一来时间复杂度就成为了O(N^2)，这显然是不可取的，效率太低，那么堆排序也就失去它存在的意义。

所以我们如果排升序的话，应该建立大堆
同样的道理，反过来，如果排降序，那我们就应该建小堆

排序操作步骤： - - 采用堆的删除思想

1. 建大堆，选出最大的数
2. 首尾元素互换，将最大的数被移到末尾
3. 然后把最后一个元素不看做堆里面的数据，接着从根节点开始向下调整，选出次大的数移至首位。
4. 再次将首位元素互换，进行上述一样的操作，直到将数组调整完毕。

代码实现：

void HeapSort(int* a, int n)
{

	// 升序 -- 大堆
	// 降序 -- 小堆
	// 建堆 -- 向下调整建堆 - O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)//(n - 1 - 1) / 2 -- (n-1)是最后一个叶子节点，再减一除2就是求最后一个节点的父节点
	{
		AdjustDown(a, n, i);
	}

	// 选数
	int i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度分析：

建堆：时间复杂度为O(N)
n次向下调整：向下调整一次是O(logN), n次就是O(NlogN)
总的时间为：NlogN + N ≈ N*logN

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

二、TOP-K问题

TOP-K问题： 再N个数里找出前K个最值

我们用求前K大数举例。

方法一：
将N个数建立成大堆，然后删除并取K次堆顶数据，这样就可以得到前K个最值
时间复杂度 为O(N+k*logN)。
但当数据量很大时，这个方法效率就有点低了，不太适合。

方法二：

1. 用前K个数建立一个K个元素的堆。
   • 若求前K大的值，建小堆
   • 若求前K小的值，建大堆
2. 剩下的N-K个数，依次和堆顶元素进行比较，若比堆顶元素大则替换堆顶元素，然后向下调整
3. 遍历完数组后，堆里的值就是前K个最大的值

建立K个数的小堆，保持小的在上面，大的在下面，每次都会把其中最小的删除出堆，而比堆顶元素大的进堆向下调整后，大的就移至下面。

void PrintTopK(int* a, int n, int k)
{
	assert(a);
	HP hp;
	HeapInit(&hp);
	//创建一个k个数的小堆
	for (int i = 0; i < k; ++i)
	{
		HeapPush(&hp, a[i]);
	}
	//剩下的N-K个数根堆顶的数据比较，比它大，就替换它
	for (int i = k; i < n; ++i)
	{
		if (a[i] > HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
			//hp.a[0] = a[i];
			//AdjustDown(hp.a, hp.size, 0);
		}
	}
	HeapPrint(&hp);
	HeapDestroy(&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

验证：