【数据结构】二叉树 —— 堆排序 + Top - K问题（详解版）_原地建堆

前言

前情回顾：二叉树 —— 堆的实现（顺序存储）

上一篇，介绍了堆（Heap）的实现，并且用堆的结构特点简单的实现了堆排序，但是之前实现的堆排序的空间复杂度是〇(N)，还可以吧继续优化。

本篇将详细讲解一下：

• 空间复杂度为〇(1)，时间复杂度为〇(N*logN)的—— “堆排序”。

---

1. 向上/下调整算法

下面两端代码是原地建堆的核心：

1.1 向上调整算法：（AdjustUp）

//向上调整算法
void AdjustUp(int* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2 向下调整算法：（AdjustDown）

//向下调整算法
void AdjustDown(int* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;//左孩子
	while (child < size)
	{
		//1.选出左右孩子中小的那一个
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		} 
		//2.如果孩子小于父亲，则交换，并继续往下调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
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

---

2. 原地建堆

原地建堆有两种方法：

• 向上建堆
• 向下建堆

这里的建堆方法和上一篇的区别是，之前的建堆是要额外开辟大小为N的数组，空间复杂度〇(N) ，这里是原地建堆，不开辟额外的空间，空间复杂度：〇(1)

2.1 向上调整建堆：

int main()
{
	int a[] = { 4,2,7,8,5,1,0,6 };
	//向上调整 -- 建堆〇(N*logN)
	int size = sizeof(a) / sizeof(int);
	for (int i = 1; i < size; i++)// 0 位置调整没价值
	{
		AdjustUp(a, i);
	}
	//打印堆
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

向上调整建立在：前面是堆的前提下。

• 这里通过for循环可以很好的将a数组中的数据一个一个入堆，并调整好，再继续入堆，直到数据入完。
• 这里并没有开辟一个新的堆，堆是依托于a数组中的。
• 入堆的顺序是先从数组a的第一个数据入堆，每次入完一个数据之后，进行一次向上调整。
• 每次调整结束之后，都有保持好堆的结构。

2.2 向下调整建堆：

int main()
{
	int a[] = { 4,2,7,8,5,1,0,6 };
	//向下调整 -- 建堆(前提:左右子树都是堆的结构)〇(N)
	int size = sizeof(a) / sizeof(int);
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, size, i);
	}
	//打印堆
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

* 不能开辟新空间，如果先将第一个数据从头往下调整的话，调完之后有可能就不是堆的结构！

• 上述图就是反例，很显然调整完之后不是大堆
• 当一堆很乱的数组从头向下调整的时候，就会有可能调过之后依旧不是堆结构。

这里依旧强调一点：向上向下调整都要建立在堆结构这个基础上！

• 向下调整建立在:根节点的左右子树都是堆的前提下
• 向上调整建立在:前面是堆的前提下

正确向下建堆方法：

• 从倒数第一个非叶子结点调(最后一个结点的父亲)，从下往上，每一棵子树都要向下调整。
  
• size - 1是最后一个元素下标，( （(size - 1) - 1） / 2 )算出他们的父亲结点
  第一个减1是最后一个元素的下标，第二个减1是公式
• 总的思路是：从下往上一个子树一个子树调
• 调过之后保证，找到的下一个根的左右子树均为堆的结构

3. 精确计算建堆的时间复杂度

3.1 向上建堆时间复杂度：

假设每次调整都是最坏的情况，每次插入时都要从堆底调到堆顶，那么总的时间复杂度该怎么算呢。

向上调整是从第二层开始调整，最坏的情况下：

• 第二层2个数据向上调1次
• 第三层4个数据向上调2次
• 第四层8个数据向上调3次
  …………
• 第h - 1 层2^(h - 2)个数据向上调(h - 2)次
• 第h 层2^(h - 1)个数据向上调(h - 1)次
• 将每次最坏的调整次数加起来
• 假设总次数为T(h)次
  

所以向上建堆的时间复杂度：〇(N*logN)

3.2 向下建堆时间复杂度：

向下调整是从倒数第二层开始调整，最坏的情况下：

• 将每次最坏的调整次数加起来
• 假设总次数为T(h)次
  还是刚刚的错位相减大法：
  

所以向下建堆的时间复杂度：〇(N)
经过较为精确的计算，我们发现，向下建堆的时间复杂度比向上建堆要好，所以我们建堆基本上都是向下建堆。

---

4. 堆排序

4.1 升序：

那么问题来了升序是建大堆好呢还是建小堆好呢？

1. 我们先来建小堆来分析一下：

• 最小的数已经在第一个位置

• 拿走堆顶最小的数之后

• 剩下的数关系全乱了，需要重新建堆(向下)，建堆要〇(N)

• 再选出次小的，不断建堆

• 那么时间复杂度就是等差数 - 时间复杂度〇(N^2)

• 如果这样，还不如直接遍历选数！搞得这么复杂。

• 遍历选数:时间复杂度〇(N)

• 这种方法可以是可以，但是效率不行，还更复杂！(不好！)

所以升序建小堆的话，时间复杂度是很不好的。

2. 那么升序建大堆会怎样呢？我们分析一下：

• 先将根节点和最后一个数交换(选出最大的数)
• 然后除去最后一个数之外，再建大堆(选出次大的数)

void HeapSort(int* a, size_t size)
{
	//向下调整 -- 建堆(前提:左右子树都是堆的结构)〇(N)
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, size, i);
	}

	size_t end = size - 1;//最后一个数据的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 4,2,7,8,5,1,0,6 };	
	HeapSort(a, sizeof(a) / sizeof(int));
	
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}
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

我们来算一下堆排序的时间复杂度：

• 建堆(向下)：〇(N)
• 排序：每次堆里的数据都出一个所以
  log2(N - 1) + log2(N - 3) + …… + log2(2) + log2(1) < log2(N^N) = N*log2(N)
• 所以总的时间复杂度：〇(N + N*log2N)
• 取大头：时间复杂度〇(N*log2N)

所以升序建大堆效果最好，和快速排序一样好。

4.2 降序：

1. 思路和上述一样，如果建大堆的话还会出现时间复杂度为〇(N^2)
2. 所以这里建小堆效果最好

• 将堆顶的数据和堆最后一个数交换
• 再从根开始向下调整

总结：

• 升序建大堆
• 降序建小堆

---

5. Top - K问题

TOP - K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top - K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

• 前k个最大的元素，则建小堆
• 前k个最小的元素，则建大堆

2. 用剩余的N - K个元素依次与堆顶元素来比较，不满足则替换堆顶元 将剩余N - K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大。

方法：

• 建立N个数的大堆，Pop K次，就可以选出最大的前K个
• 时间复杂度〇(N + logN*K) 空间复杂度〇(1)

这样虽然可以，但是当处理海量数据的时候，就会出现内存不够的现象

没那么大内存的电脑！

如何求解：

• 用前K个数建立一个K个数的小堆,然后剩下的 N - K 个数依次遍历，
• 如果比堆顶的数据大，就替换它进堆，最后堆里的K个数就是最大的K个。
• 进堆:替换之后，向下调整。
• 时间复杂度〇(K + (N-K)*logK) 空间复杂度〇(K)的元素。

void PrintTopK(int* a, int n, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	int* KminHeap = (int*)malloc(sizeof(int) * k);
	assert(KminHeap);

	//进堆
	for (int i = 0; i < k; i++)
	{
		KminHeap[i] = a[i];
	}

	//建小堆 - 向下建堆
	for (int j = (k - 1 - 1) / 2; j >= 0; j--)
	{
		AdjustDown(KminHeap, k, j);
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则替换
	for (int i = k; i < n; i++)
	{
		if (a[i] > KminHeap[0])
		{
			KminHeap[0] = a[i];
			AdjustDown(KminHeap, k, 0);
		}
	}

	for (int j = 0; j < k; j++)
	{
		printf("%d ", KminHeap[j]);
	}
	printf("\n");
	free(KminHeap);

}

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	assert(a);
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		a[i] = (int)rand() % 1000000;
	}

	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}

int main()
{
	TestTopk();
	return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

通过设置随机值将所有的数设置成1000000以内的数，再随便设置是个数大于1000000，最后的结果一定是这十个数。

这里不是有序的，只是一个小堆的结构，因为堆不一定有序。

6. 总结

堆 ： 数组实现堆，实际上操纵的是一个数组，逻辑上想象的是完全二叉树！