二叉堆&堆排序
什么是二叉堆？
二叉堆本质上是一种完全二叉树，它分为两个类型：
1.最大堆（max heap，又称大顶堆、大根堆）
2.最小堆（min heap，又称小顶堆、小根堆）
最大堆就是任何一个父节点的值，都大于等于它左右孩子节点的值。
同理，最小堆就是任何一个父节点的值，都小于等于它左右孩子节点的值。
如何构建一个堆
构建堆主要依靠堆得自我调整
堆的自我调整
对于二叉堆，如下有几种操作：
插入节点
删除节点
构建二叉堆
这几种操作都是基于堆的自我调整。
下面让我们以最小堆为例，看一看二叉堆是如何进行自我调整的。
插入节点
二叉堆的节点插入，插入位置是完全二叉树的最后一个位置。比如我们插入一个新节点，值是 0。
这时候，我们让节点0的它的父节点5做比较，如果0小于5，则让新节点“上浮”，和父节点交换位置。
继续用节点0和父节点3做比较，如果0小于3，则让新节点继续“上浮”。
继续比较，最终让新节点0上浮到了堆顶位置。
删除节点
二叉堆的节点删除过程和插入过程正好相反，所删除的是处于堆顶的节点。比如我们删除最小堆的堆顶节点1。
这时候，为了维持完全二叉树的结构，我们把堆的最后一个节点10补到原本堆顶的位置。
接下来我们让移动到堆顶的节点10和它的左右孩子进行比较，如果左右孩子中最小的一个（显然是节点2）比节点10小，那么让节点10“下沉”。
继续让节点10和它的左右孩子做比较，左右孩子中最小的是节点7，由于10大于7，让节点10继续“下沉”。
这样一来，二叉堆重新得到了调整。
构建二叉堆
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。
我们举一个无序完全二叉树的例子：
首先，我们从最后一个非叶子节点开始，也就是从节点10开始。如果节点10大于它左右孩子中最小的一个，则节点10下沉。
接下来轮到节点3，如果节点3大于它左右孩子中最小的一个，则节点3下沉。
接下来轮到节点1，如果节点1大于它左右孩子中最小的一个，则节点1下沉。事实上节点1小于它的左右孩子，所以不用改变。
接下来轮到节点7，如果节点7大于它左右孩子中最小的一个，则节点7下沉。
节点7继续比较，继续下沉。
这样一来，一颗无序的完全二叉树就构建成了一个最小堆。
堆的代码实现
在撸代码之前，我们还需要明确一点：
二叉堆虽然是一颗完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组当中。
数组中，在没有左右指针的情况下，如何定位到一个父节点的左孩子和右孩子呢？
像图中那样，我们可以依靠数组下标来计算。
假设父节点的下标是parent，那么它的左孩子下标就是 2*parent+1；它的右孩子下标就是 2*parent+2 。
比如上面例子中，节点6包含9和10两个孩子，节点6在数组中的下标是3，节点9在数组中的下标是7，节点10在数组中的下标是8。
7 = 3*2+1
8 = 3*2+2
刚好符合规律。
有了这个前提，下面的代码就更好理解了：
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
import java.util.Arrays;
public class {
public static void upAdjust(int[] array) {
int childIndex = array.length - 1;
int parentIndex = (childIndex - 1) / 2;
int temp = array[childIndex];
while (childIndex > 0 && temp < array[parentIndex]) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
array[childIndex] = temp;
}
public static void downAdjust(int[] array, int parentIndex, int length) {
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}
if (temp <= array[childIndex])
break;
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}
public static void buildHeap(int[] array) {
for (int i = array.length / 2; i >= 0; i--) {
downAdjust(array, i, array.length - 1);
}
}
public static void main(String[] args) {
int[] array = new int[] { 1, 3, 2, 6, 5, 7, 8, 9, 10, 0 };
upAdjust(array);
System.out.println(Arrays.toString(array));
array = new int[] { 7, 1, 3, 10, 5, 2, 8, 9, 6 };
buildHeap(array);
System.out.println(Arrays.toString(array));
}
}
|
代码中有一个优化的点，就是父节点和孩子节点做连续交换时，并不一定要真的交换，只需要先把交换一方的值存入temp变量，做单向覆盖，循环结束后，再把temp的值存入交换后的最终位置。
堆排序
让我们回顾一下二叉堆和最大堆的特性：
1.二叉堆本质上是一种完全二叉树
2.最大堆的堆顶是整个堆中的最大元素
当我们删除一个最大堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。
正如上图所示，当我们删除值为10的堆顶节点，经过调节，值为9的新节点就会顶替上来；当我们删除值为9的堆顶节点，经过调节，值为8的新节点就会顶替上来…….
由于二叉堆的这个特性，我们每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶，反复调节二叉堆，所得到的集合就成为了一个有序集合，过程如下：
删除节点9，节点8成为新堆顶：
删除节点8，节点7成为新堆顶：
删除节点7，节点6成为新堆顶：
删除节点6，节点5成为新堆顶：
删除节点5，节点4成为新堆顶：
删除节点4，节点3成为新堆顶：
删除节点3，节点2成为新堆顶：
到此为止，我们原本的最大堆已经变成了一个从小到大的有序集合。之前说过二叉堆实际存储在数组当中，数组中的元素排列如下：
由此，我们可以归纳出堆排序算法的步骤：
1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。
代码在二叉堆操作的基础上稍加改动就行
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
|
import java.util.Arrays;
public class HeapSort {
public static void downAdjust(int[] array, int parentIndex, int length) {
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
childIndex++;
}
if (temp >= array[childIndex])
break;
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}
public static void heapSort(int[] array) {
for (int i = (array.length - 2) / 2; i >= 0; i--) {
downAdjust(array, i, array.length);
}
System.out.println(Arrays.toString(array));
for (int i = array.length - 1; i > 0; i--) {
int temp = array[i];
array[i] = array[0];
array[0] = temp;
downAdjust(array, 0, i);
}
}
public static void main(String[] args) {
int[] arr = new int[] { 1, 3, 2, 6, 5, 7, 8, 9, 10, 0 };
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
|
二叉堆的节点下沉调整（downAdjust 方法）是堆排序算法的基础，这个调节操作本身的时间复杂度是多少呢？
假设二叉堆总共有n个元素，那么下沉调整的最坏时间复杂度就等同于二叉堆的高度，也就是O（logn）。
我们再来回顾一下堆排序算法的步骤：
- 把无序数组构建成二叉堆。
- 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。
第一步，把无序数组构建成二叉堆，需要进行n/2次循环。每次循环调用一次 downAdjust 方法，所以第一步的计算规模是 n/2 * logn，时间复杂度O（nlogn）。
第二步，需要进行n-1次循环。每次循环调用一次 downAdjust 方法，所以第二步的计算规模是 （n-1） * logn ，时间复杂度 O（nlogn）。
两个步骤是并列关系，所以整体的时间复杂度同样是 O（nlogn）。
近期评论