数据结构——堆排序

本文介绍堆排序的思想和代码

基本思想

  • 生成最大堆(heapify)：从倒数第一个非叶节点开始，按照下虑操作找到该节点在最大堆中的位置，逐步遍历每一个非叶结点执行上述操作，生成最大堆
  • 交换最大值到末尾：交换根节点与最后一个元素的值，树节点减少1（刚才根节点是当前树的最大值，更换以后就是有序的元素了，不再参与最大堆调整）
  • 重新生成最大堆（调整根节点）：调整新换上来的根节点（下虑操作），找到其应该在的地方，重新生成最大堆
  • 循环交换根节点和调整根节点这两个步骤，直到最大堆只剩下一个元素

代码实现

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
// 堆排序实现，对长度为n的数组a进行排序
void HeapSort(int* a, int n) 
{
    // 生成堆 heapify
	for (int i = n/2-1; i >= 0; --i) // 从n/2-1开始，找到最大的非叶节点
	{
		AdjustDown(a, n, i); // 将第i个节点按照下虑操作放置到它在最大堆中应该在的地方，注意本函数执行完后，当前节点i的所有子节点都小于等于节点i，也就是说，在最终生成的最大堆中，节点i的位置不会再更靠后了，详情见后面函数的实现
	}
	int end = n - 1; // 用于表示数组尾部结点的下标 数值表示此前数字个数
	while (end > 0)
	{
		Swap(&a[0], &a[end]); // 将根部数据排在最后 达到升序的效果
		AdjustDown(a, end, 0);
		--end; // 将从根部换下的值不当作堆中数据 对堆重复以上操作
	}
}

// 最大堆的下虑操作实现：将 数组a的前size个数 所表达的最大堆的 parent节点 通过下虑操作找到其应在的位置
void AdjustDown(int* a, int size, int parent)//向下调整（O(logn)）
{
	// 假设法，假设最大孩子节点是左节点
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 大堆中 向下调整 找大的孩子节点
		if (child + 1 < size && a[child] < a[child + 1]) // 假设错误，右孩子大于左孩子
		{
			child++; // 更新为右孩子
		}
		if (a[child] > a[parent]) // 如果不符合最大堆规则，将父节点与最大的孩子节点进行交换
		{
			Swap(&a[child], &a[parent]); // 交换完成
			// 更新父节点和子节点
			parent = child; // 此时的父节点变为孩子节点所在位置（还是入参parent对应的那个数字），需要继续进行下一轮最大堆验证
			child = parent * 2 + 1; // 依然假设法，假设最大孩子节点是左节点
		}
		else // 如果满足最大堆规则，终止
		{
			break;
		}
	}
}