堆的实现与应用

---

前言

上一期我们学习了堆，这一期我们来了解堆的一些应用
上一期的堆各个函数接口代码

一、堆的实现

我们前面学习了向上调整方法和向下调整方法，那么究竟哪一种方法更好呢？
这里就为大家解释

1、建堆方式

向上调整建堆：

for (int i = 0; i < n; ++i)//创建堆
{//从第一个数据开始，每个数据都当成一个堆，进行向上调整
	Justup(a, i);//向上调整建堆--时间复杂度O(N*logN)
}
1
2
3
4

向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

那么如果左右子树不是堆呢？
这里既然没有条件我们就创造条件

向下调整建堆第一步：

for (int i = (n - 1 - 1) / 2; i >= 0; --i)//创建堆
{//n-1-1然后/2是最后一个节点的父亲节点
	Justdown(a, n, i);//向下调整建堆时间复杂度O(N)
}
1
2
3
4

这里就有人问了，为什么向下调整建堆是从（n-1-1）/2的地方开始的?
这是因为：每一个叶节点都没有子节点，所以每一个叶节点的位置都是正确的，那么我们就需要从倒数第一个非叶子节点开始进行向下调整，通过前面的公式我们知道——父节点=（子节点-1）/2，那么最后一个子节点下标就是n-1，所以n-1-1再除以2就是最后一个非叶子节点。然后我们一直调整到根节点的树，就可以调整成堆

那么又有人说了，就算是从倒数第一个节点开始，到根节点用大O渐进法不应该还是n吗？向下调整的时间复杂度是O（logN），这样子算下来不是O(N*logN)吗？其实不是这样的。

2、建堆的时间复杂度

向下建堆时间复杂度：
这里用到了高中的错位相减法，就算大家全部忘记了，看到公式其实很容易想起来

这里再细说一下：
n是树的节点：n=2^h-1;
h是树的高度:h=log(n+1);
T(n)就是时间复杂度（每一个节点移动最多层数之和）：T(n)=n-log(n+1)约等于O（N）(也就是每一个节点到最后一层的距离之和)
所以计算之后，通过大O渐进表示法，时间复杂度为O(N);

向上调整的时间复杂度就不算了，但是可以明确告诉大家，向上调整最后一层的时间复杂度就已经来到了O(N*logN)

二、堆的应用

堆排序大思路：选择排序，依次选数，从后往前排

1、堆排序

这里我们不采用前面的Top和Pop函数，因为堆排序我们是可以直接使用的，不需要先写一个堆出来。其次Top和Pop空间复杂度过高，写一个堆需要建空间的，我们可以直接对数据进行操作，不需要开辟另外的空间

我们来看看排序问题：
上面我们知道了堆要先创建出来才能执行后面的操作

那么排序的话，排升序是建大堆还是小堆，排降序建大堆还是小堆呢？

是不是有很多人就想着升序建小堆，降序建大堆呢？因为小堆最小的数据在堆顶，大堆最大的数在堆顶。
这种方法的确可行，但是代价太大了。我们举个升序建小堆的例子：

我们直接给出一组小堆数据：【1，4，19，15，7，34，65，25，27，28】
（画的有点难看，席位各位别建议）

我们如何依次选出次小的数据呢？
先提出1，把剩下数据看成堆。那么4就到了根位置上面

这个时候节点之间的父子关系就全乱了（与上一期堆的删除接口一样），我们上一张图片中建的小堆的优势全部没有了。这个时候4才是根。那么提取出1，再想提取出次小值就要重新建堆来选择了。如果提取一个小值就要建一次堆这样的复杂度太高了，代价太大了

所以，我们排升序就要建大堆，排降序就要建小堆

首先是建堆：
直接用向下调整方法建堆

for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
	Justdown(a, n, i);
}
1
2
3
4

然后就是选数了：

int i = 1;//i从1开始
while (i < n)
{
	Swap(&a[0], &a[n - i]);//交换第一个数据和最后一个数据
	Justdown(a, n - i, 0);//向下调整，每次调整都不考虑交换后的末尾数据
	++i;
}
1
2
3
4
5
6
7

刚好符合：

二、TOP-K问题

题目描述：

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

最佳的方式就是用堆来解决，基本思路如下：

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

这里就又有一个问题了，如果找前k个最大的数据，建大堆还是建小堆呢？
答案是：都可以

建堆

1、建大堆：选k次即可，也急速Popk次。（出来的数据直接是有序的）时间复杂度：O(N+logN*K)
但是建大堆有缺陷：如果n很大，k很小，n远大于k。（比如：n=10万亿，k=100），这样建大堆就不行了，因为要建n个数的大堆的话数据在内存存不下，只能存硬盘里面

2、建小堆：建k个数的小堆出来。（结果无序） 时间复杂度：O(K+logK*(n-k))，如果n远大于k，那么时间复杂度就是O(N)
第一步：用前k个数建一个小堆
第二步：遍历第k+1个数到din个数，如果遍历数据比堆顶数据大就替换堆顶数据，然后向下调整。此时堆里面的数据就是最大的前k个数

完整代码

void PrintTopK(int* a, int n, int k)
{
	// 1 . 建堆- -用a中前k个元素建堆
	//建k个数的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		Justdown(a, k, i);
	}
	// 2 . 将剩余n - k个元素依次与堆顶元素交换，不满则则替换
	//读取后n-k个数据
	for (int i = k; i < n; ++i)
	{
		if (a[i] > a[0])
		{
			a[0] = a[i];
			Justdown(a, k, 0);
		}
	}
	//打印小堆值，不是有序的
	for (int i = 0; i < k; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = 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

总结：

到目前为止，我们关于堆的学习就告一段落了，接下来我们将继续学习二叉树的递归等操作，希望大家多多支持