0%

排序-堆排序

发表于 更新于 分类于

概念

堆： 堆是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子（如果存在的话）的值，称为最大堆；或者每个节点的值都小于或等于其左右孩子（如果存在的话）的值，称为最小堆。

完全二叉树：

complete binary tree

最大堆：

max heap

最小堆：

min heap

图片来源: 常见排序算法 - 堆排序 (Heap Sort)

堆排序：利用堆（这里使用最大堆）进行排序的方法。其基本思想是：将待排序的序列构造成一个最大堆，此时待排序序列的最大值就是堆顶的根节点，将其移走（其实就是将其与待排序序列的最后一个元素进行交换，此时待排序序列最后一个元素就是最大值），然后将剩余的序列重新构造成一个堆，如此反复，直到待排序序列只有一个元素为止，则排序完成。

性质

已知arr[0…n-1]是长度为n的最大堆数组，下标从0开始，那么对于下标为 i 的节点 I ，有：
(1). 如果 I 的左孩子存在的话，那么I的左孩子节点的下标为 left(i) = 2*i+1；
(2). 如果 I 的右孩子存在的话，那么I的右孩子节点的下标为 right(i) = 2*i+2;
(3). 如果 I 双亲节点存在的话，那么I的双亲节点的下标为 parent(i) = (i-1)/2; (向下取整)

基本操作

  1. 构建最大堆 buildMaxHeap(int[] arr)：将待排序序列arr构建成最大堆；
  2. 调整最大堆 adjustHeap(int arr[], int begin, int end): 已知arr[begin]的左子树和右子树都满足最大堆，那么调节节点arr[begin]，将以arr[begin]为根节点的二叉树调整为最大堆。

对于堆排序，最重要的就是构建最大堆和调整最大堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

Java实现

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 定义接口
interface Sorter {
	/**
	 * 将数组按升序排序
	 */
	int[] sort(int[] arr);

	/**
	 * 交换数组arr中的第i个位置和第j个位置的关键字
	 */
	default void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}
// 堆排序
class HeapSorter implements Sorter {

	@Override
	public int[] sort(int[] arr) {
		heapSort(arr);
		return arr;
	}

	private void heapSort(int[] arr) {

		buildMaxHeap(arr); // 构建最大堆

		// 将最大堆堆顶元素与数组末尾元素交换，并将前n-1序列重新构造成最大堆,重复n-1次
		for (int i = arr.length - 1; i >= 1; i--) {
			swap(arr, 0, i); // 将堆顶元素和当前未经排序的子序列的最后一个元素进行交换
			adjustHeap(arr, 0, i - 1); // 将arr[0...i-1](前i个元素)重新调整为最大堆
		}
	}

	/**
	 * 将指定数组arr构建成最大堆
	 */
	private void buildMaxHeap(int[] arr) {
		int len = arr.length;
		// 从最后一个非叶子节点往前遍历，将当前序列构成最大堆
		for (int i = len / 2 - 1; i >= 0; i--) {
			adjustHeap(arr, i, len - 1);
		}
	}

	/**
	 * 假定arr[begin]的左子树和右子树均满足最大堆，那么调节节点arr[begin]，将以arr[begin]为根节点的二叉树调整为最大堆。
	 */
	private void adjustHeap(int[] arr, int begin, int end) {
		int tmp = arr[begin];
		int j;
		for (j = 2 * begin + 1; j <= end; j = 2 * j + 1) {
			// j=2*begin+1表示j对应二叉树节点的左孩子
			if (j + 1 <= end && arr[j] < arr[j + 1]) {
				// 如果当前节点的右孩子存在且左孩子的值小于右孩子
				j++; // j为左右孩子较大记录的下标
			}
			if (tmp >= arr[j]) // tmp的值已经大于arr[j]，则调整完毕，跳出循环
				break;
			arr[begin] = arr[j]; // 当前根节点并未均大于左右节点(如果有的话)，重新给当前根节点赋值
			begin = j; // begin指向新的可能需要进行最大堆调整的子树的根节点
		}
		arr[begin] = tmp;
	}
}

堆排序其实也是一种选择排序，是一种树形选择排序。在简单选择排序中，从arr[0…n-1]中选择最小（或最大）记录，需要比较n-1次，然后再从剩下arr[1…n-1]的n-1个元素中选择最小（或最大）记录，需要比较n-2次。然而事实上这n-2次比较中，有许多已经在前一趟n-1次的比较中做过了；而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数，提高算法效率。

复杂度

时间复杂度：
对于n个关键字序列，每个节点需比较log2(n)次，因此其时间复杂度为O(nlogn)。
由于堆排序对原始记录的排序状态并不敏感，所以它的最好、最坏、平均时间复杂度均为O(nlogn)
由于初始构建堆所需要的比较次数较多，所以堆排序不适合待排序序列个数少的情况。

空间复杂度：
最好情况=平均情况=最坏情况=O(1)

参考链接

推排序
常见排序算法 - 堆排序 (Heap Sort)
堆排序(Heap Sort)算法学习