ACM教程 - 堆排序

定义

堆是一种叫做完全二叉树的数据结构。这里我们用到两种堆，其实也算是一种。

• 大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
• 小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

​

Ps：小顶堆有误，节点3 和 节点2 换下位置！

如上所示，就是两种堆。如果我们把这种逻辑结构映射到数组中，就是下边这样

9

5

8

2

3

4

7

1

1

2

5

4

3

8

9

7

这个数组 arr 逻辑上就是一个堆。从这里我们可以得出以下性质（重点）

1. 对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]
2. 对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

• 稳定性：根据 相等元素 在数组中的 相对顺序 是否被改变，排序算法可分为「稳定排序」和「非稳定排序」两类。
• 就地性：根据排序过程中 是否使用额外内存（辅助数组），排序算法可分为「原地排序」和「异地排序」两类。一般地，由于不使用外部内存，原地排序相比非原地排序的执行效率更高。
• 自适应性：根据算法 时间复杂度 是否 受待排序数组的元素分布影响 ，排序算法可分为「自适应排序」和「非自适应排序」两类。「自适应排序」的时间复杂度受元素分布影响，反之不受其影响。
• 比较类：比较类排序基于元素之间的 比较算子（小于、相等、大于）来决定元素的相对顺序；相对的，非比较排序则不基于比较算子实现。

图解

4

5

8

2

3

9

7

1

以该数组为例，构建最大堆实现从小到大排序，几个要点如下

1. 一开始构建最大堆，从最后一个非叶子节点开始直到根节点进行自底向上（从下到上，从右到左）
2. 轮到自己节点时（当前作为父节点来看待），分别比较自己的左子节点和右子节点，最终判断出最大的节点，如果最大节点是自己本身，不交换；否则自己节点和最大节点进行交换
3. 如果第 2 点不存在交换（跳过第 3 点），否则继续将换下去的子节点（原本是父节点，没错吧），继续往下维护同样的比较操作，直到没有节点了为止

• 以上构建最大堆完毕，接下来开始真正的堆排序，第一次构建完，根节点一定是最大值，换到最后 1 个叶子节点，此时最后 1 个节点到了根节点，再进行维护堆，就又会产生第 2 个最大值，然后再次将该根节点交换到倒数第 2 个叶子节点，依此类推。完毕（因为篇幅有限，只罗列解释中关键几个中间过程图例）

  

性质

• 时间复杂度
  • 最佳 O(nlogn)
  • 平均 O(nlogn)
  • 最差 O(​​​​​​​nlogn)
• 空间复杂度
  • 最差 O(1)
• 稳定性：不稳定
• 就地性：原地
• 自适应性：非自适应
• 比较类：比较 

Java

public class HeapSort {
 
    // 入口在这
	public static void heapSort(int[] arr) {
		if (arr == null || arr.length == 0) {
			return;
		}
		int len = arr.length;
		// 构建大顶堆，这里其实就是把待排序序列，变成一个大顶堆结构的数组
		buildMaxHeap(arr, len);
 
		// 交换堆顶和当前末尾的节点，重置大顶堆
		for (int i = len - 1; i > 0; i--) {
			swap(arr, 0, i);
			len--;
			heapify(arr, 0, len);
		}
	}
 
	private static void buildMaxHeap(int[] arr, int len) {
		// 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
		for (int i = (len - 1) / 2; i >= 0; i--) {
			heapify(arr, i, len);
		}
	}
 
	private static void heapify(int[] arr, int i, int len) {
		// 先根据堆性质，找出它左右节点的索引
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		// 默认当前节点（父节点）是最大值。
		int largestIndex = i;
		if (left < len && arr[left] > arr[largestIndex]) {
			// 如果有左节点，并且左节点的值更大，更新最大值的索引
			largestIndex = left;
		}
		if (right < len && arr[right] > arr[largestIndex]) {
			// 如果有右节点，并且右节点的值更大，更新最大值的索引
			largestIndex = right;
		}
 
		if (largestIndex != i) {
			// 如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换
			swap(arr, i, largestIndex);
			// 因为互换之后，子节点的值变了，如果该子节点也有自己的子节点，仍需要再次调整。
			heapify(arr, largestIndex, len);
		}
	}
 
	private static void swap (int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}