【排序算法】四、堆排序（C/C++）

堆排序

1.1 原理

堆是一种特殊的树形数据结构，它满足以下两个性质：

堆是一棵完全二叉树
堆中每个节点的值都必须大于等于（或小于等于）其子节点的值，这样的堆称为大根堆（或小根堆）

堆排序算法的核心就是利用堆的性质来实现排序，堆这里就不详细介绍了（在数据结构——堆中已经详细介绍）

堆排序采用的是堆的向下调整算法（为什么选这个，在数据结构——堆中已经详细介绍）

堆排序想要对排序的数进行升序排序：建小根堆（小堆）
想要对排序的数进行降序排序：建大根堆（大堆）
小根堆：在小根堆中，任意节点的值都小于或等于其子节点的值（最小值在根节点）
大根堆：在大根堆中，任意节点的值都大于或等于其子节点的值（最大值在根节点）

先构建堆：将待排序的序列构建成一个大堆（或小堆）
再调整堆：将堆顶元素与堆的最后一个元素交换，并重新调整堆，使得剩余元素仍然满足堆的性质
重复步骤2，直到所有元素都排好序

：需要注意的是排升序要建大堆，排降序建小堆

下面介绍堆的向下调整

1.2 堆的向下调整

堆向下调整算法的基本思想是将堆中的某个节点按照堆的性质向下调整，使得以该节点为根的子树重新成为一个堆。具体步骤如下：

首先确定需要调整的节点的左右子节点中的较大值（或较小值，根据堆的性质而定）
将该节点与其左右子节点中的较大值（或较小值）进行比较，如果该节点的值不符合堆的性质（小堆或大堆），则交换两者的位置
继续对交换后的节点进行向下调整，直到该节点的值符合堆的性质或者已经没有子节点可以进行比较为止

通过这样的向下调整操作，可以保持堆的性质不变，并且在插入或删除节点之后，可以快速地恢复堆的性质

从根结点处开始，选出左右孩子中值较小的孩子
让小的孩子与其父亲进行比较
若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换
并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止
若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆

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

假设向下调整27，如图所示：
【排序算法】四、堆排序（C/C++）-LMLPHP
堆的向下调整算法代码：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 堆的向下调整（下面是小堆：降序）
void AdjustDown(int* arr, int n, int parent) // n:arr数组的大小; parent:父节点的数组下标
{
	// 左子节点下标为parent * 2 + 1; 右子节点的下标为parent * 2 + 2
	int child = parent * 2 + 1; // 假设左孩子较大
	// 
	while (child < n)
	{
		// 选出左右孩子中小的那个
		if ((child + 1 < n) && arr[child] > arr[child + 1]) // child + 1:右孩子的下标；-- 右孩子存在，并且左孩子比右孩子大
		{
			++child;
		}
		// 孩子跟父亲比较
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]); // 交换数据
			//迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

：若父节点下标为parent，左子节点下标为parent * 2 + 1，右子节点的下标为parent * 2 + 2

修改一下，判断条件即可

// ...
if ((child + 1 < n) && arr[child] < arr[child + 1])
// ...
if (arr[child] < arr[parent])
// ...

使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：h-1次（h为树的高度）
而h = log(N+1)（N为树的总结点数，log以2为底）
所以堆的向下调整算法的时间复杂度为：O(logN)

1.3 堆排序代码实现

前面说到，使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？

只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可

// 1.建堆
// 向下调整建堆方式时间复杂度：O(N)
// 从第一个非叶子结点开始向下调整，一直到根
for (int i = (n - 1 - 1) / 2; i >= 0; --i) // n-1:数组下标上限，(n-1-1)/2:孩子的父亲节点
{
	AdjustDown(arr, n, i);
}

以建小堆为例，如图所示：

第一次向下调整：（非叶子节点开始）
第二次向下调整：
第三次向下调整：
第四次向下调整：
第五次向下调整：（到根节点结束）

建堆
调整（即排序的过程）

堆排序代码如下：

//堆排序
void HeapSort(int* arr, int n) // n:数组大小
{
	// 1.建堆
	// 向下调整建堆方式时间复杂度：O(N)
	// 从第一个非叶子结点开始向下调整，一直到根
	for (int i = (n - 1 - 1) / 2; i >= 0; --i) // n-1:数组下标上限，(n-1-1)/2:孩子的父亲节点
	{
		AdjustDown(arr, n, i);
	}

	// 2.调整（排序的过程）
	// 调整时间复杂度：O(N*logN)
	int end = n - 1; // 记录堆的最后一个数据的下标
	while (end > 0)
	{
		// 堆顶数据与堆的最后一个数据交换
		Swap(&arr[0], &arr[end]);
		// 进行调整
		AdjustDown(arr, end, 0); // 对根进行一次向下调整
		end--; // 堆的最后一个数据的下标减一
	}
}

建堆的时间复杂度：

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明（时间复杂度本来看的就是近似值，多几个节点不影响最终结果）
【排序算法】四、堆排序（C/C++）-LMLPHP
计算建堆过程中总共交换的次数：

① T ( n ) = 2 0 ∗ ( h − 1 ) + 2 1 ∗ ( h − 2 ) + 2 2 ∗ ( h − 3 ) + . . . + 2 h − 3 ∗ 2 + 2 h − 2 ∗ 1 ① T(n)=2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+...+2^{h-3}*2+2^{h-2}*1 ①T(n)=20∗(h−1)+21∗(h−2)+22∗(h−3)+...+2h−3∗2+2h−2∗1

两边同时乘2得：（等差数列乘以一个等比数列，使用裂项相消法进行化简）

② 2 T ( n ) = 2 1 ∗ ( h − 1 ) + 2 2 ∗ ( h − 2 ) + 2 2 ∗ ( h − 3 ) + . . . + 2 h − 2 ∗ 2 + 2 h − 1 ∗ 1 ②2 T(n)=2^1*(h-1)+2^2*(h-2)+2^2*(h-3)+...+2^{h-2}*2+2^{h-1}*1 ②2T(n)=21∗(h−1)+22∗(h−2)+22∗(h−3)+...+2h−2∗2+2h−1∗1

②-①两式相减得：（错位相减）

T ( n ) = 1 − h + 2 1 + 2 3 + . . . + 2 h − 2 + 2 h − 1 T(n)=1-h+2^1+2^3+...+2^{h-2}+2^{h-1} T(n)=1−h+21+23+...+2h−2+2h−1

T ( n ) = 2 0 + 2 1 + 2 3 + . . . + 2 h − 2 + 2 h − 1 − h T(n)=2^0+2^1+2^3+...+2^{h-2}+2^{h-1}-h T(n)=20+21+23+...+2h−2+2h−1−h

运用等比数列求和得：

T ( n ) = 2 h − h − 1 T(n)=2^h-h-1 T(n)=2h−h−1

由二叉树的性质，有 N = 2 h − 1 N=2^h-1 N=2h−1和 h = l o g 2 ( N + 1 ) h=log_2(N+1) h=log2(N+1)，于是：

T ( n ) = N − l o g 2 ( N + 1 ) ≈ N T(n)=N-log_2(N+1)≈N T(n)=N−log2(N+1)≈N

用大O的渐进表示法，即：

T ( n ) = O ( N ) T(n)=O(N) T(n)=O(N)

因此：建堆的时间复杂度为O(N)

排序时间复杂度：

每次进行堆的向上调整时间复杂度为O(logN)
数组一共有n个元素
进行排序的时间复杂度为：O(nlogn)

1.3 性质总结

时间复杂度：堆排序的平均时间复杂度为 O(nlogn)，最坏情况下也为 O(nlogn)
空间复杂度：O(1)
不稳定性：堆排序是一种不稳定的排序算法，即相同元素的相对位置可能会发生变化
适用范围：堆排序适用于大数据量的排序，对于小数据量的排序效率较低

--------------------- END ----------------------

「 作者 」 枫叶先生
「 更新 」 2024.1.11
「 声明 」 余之才疏学浅，故所撰文疏漏难免，
          或有谬误或不准确之处，敬请读者批评指正。

枫叶先生