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

文章目录

前言
1. 向上/下调整算法
- - 1.1 向上调整算法：（AdjustUp）
  - 1.2 向下调整算法：（AdjustDown）
2. 原地建堆
- - 2.1 向上调整建堆：
  - 2.2 向下调整建堆：
3. 精确计算建堆的时间复杂度
- - 3.1 向上建堆时间复杂度：
  - 3.2 向下建堆时间复杂度：
4. 堆排序
- - 4.1 升序：
  - 4.2 降序：
5. Top - K问题
6. 总结

前言

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

上一篇，介绍了堆（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 向下调整算法：（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;
		}
	}
}

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

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

这里通过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;
}

不能开辟新空间，如果先将第一个数据从头往下调整的话，调完之后有可能就不是堆的结构！
上述图就是反例，很显然调整完之后不是大堆
当一堆很乱的数组从头向下调整的时候，就会有可能调过之后依旧不是堆结构。

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

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

正确向下建堆方法：

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

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 升序：

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

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

最小的数已经在第一个位置
拿走堆顶最小的数之后
剩下的数关系全乱了，需要重新建堆(向下)，建堆要〇(N)
再选出次小的，不断建堆
那么时间复杂度就是等差数 - 时间复杂度〇(N^2)
如果这样，还不如直接遍历选数！搞得这么复杂。
遍历选数:时间复杂度〇(N)
这种方法可以是可以，但是效率不行，还更复杂！(不好！)

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

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

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

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

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

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

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

4.2 降序：

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

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

总结：

升序建大堆
降序建小堆

5. Top - K问题

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

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

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

用剩余的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;
}