3.3.1 初识二叉堆
什么是二叉堆?
二叉堆本质上是一种完全二叉树,它分为两个类型。
1. 最大堆。
2. 最小堆。
什么是最大堆呢?最大堆的任何一个父节点的值,都大于或等于 它左、右孩子节点的值。
什么是最小堆呢?最小堆的任何一个父节点的值,都小于或等于它左、右孩子节点的值。
二叉堆的根节点叫作堆顶 。
最大堆和最小堆的特点决定了:最大堆的堆顶是整个堆中的最大元素 ;最小堆的堆顶是整个堆中的最小元素 。
那么,我们如何构建一个堆呢?
这就需要依靠二叉堆的自我调整了。
3.3.2 二叉堆的自我调整
对于二叉堆,有如下几种操作。
1. 插入节点。
2. 删除节点。
3. 构建二叉堆。
这几种操作都基于堆的自我调整。所谓堆的自我调整,就是把一个不符合堆性质的完全二叉树,调整成一个堆。下面让我们以最小堆为例,看一看二叉堆是如何进行自我调整的。
1. 插入节点
当二叉堆插入节点时,插入位置是完全二叉树的最后一个位置。例如插入一个新节点,值是 0。
这时,新节点的父节点5比0大,显然不符合最小堆的性质。于是让新节点“上浮”,和父节点交换位置。
继续用节点0和父节点3做比较,因为0小于3,则让新节点继续“上浮”。
继续比较,最终新节点0“上浮”到了堆顶位置。
2. 删除节点
二叉堆删除节点的过程和插入节点的过程正好相反,所删除的是处于堆顶的节点。例如删除最小堆的堆顶节点1。
这时,为了继续维持完全二叉树的结构,我们把堆的最后一个节点10临时补到原本堆顶的位置。
接下来,让暂处堆顶位置的节点10和它的左、右孩子进行比较,如果左、右孩子节点中最小的一个(显然是节点2)比节点10小,那么让节点10“下沉”。
继续让节点10和它的左、右孩子做比较,左、右孩子中最小的是节点7,由于10大于7,让节点10继续“下沉”。
这样一来,二叉堆重新得到了调整。
3. 构建二叉堆
构建二叉堆,也就是把一个无序的完全二叉树调整为二叉堆,本质就是让所有非叶子节点依次“下沉” 。
下面举一个无序完全二叉树的例子,如下图所示。
首先,从最后一个非叶子节点开始,也就是从节点10开始。如果节点10大于它左、右孩子节点中最小的一个,则节点10“下沉”。
接下来轮到节点3,如果节点3大于它左、右孩子节点中最小的一个,则节点3“下沉”。
然后轮到节点1,如果节点1大于它左、右孩子节点中最小的一个,则节点1“下沉”。事实上节点1小于它的左、右孩子,所以不用改变。
接下来轮到节点7,如果节点7大于它左、右孩子节点中最小的一个,则节点7“下沉”。
节点7继续比较,继续“下沉”。
经过上述几轮比较和“下沉”操作,最终每一节点都小于它的左、右孩子节点,一个无序的完全二叉树就被构建成了一个最小堆。
小灰,你来思考一下,堆的插入、删除、构建操作的时间复杂度各是多少?
堆的插入操作是单一节点的“上浮”,堆的删除操作是单一节点的“下沉”,这两个操作的平均交换次数都是堆高度的一半,所以时间复杂度是O(logn)。至于堆的构建,需要所有非叶子节点依次“下沉”,所以我觉得时间复杂度应该是O(nlogn)吧?
关于堆的插入和删除操作,你说的没有错,时间复杂度确实是O(logn)。但构建堆的时间复杂度却并不是O(nlogn),而是O(n)。这涉及数学推导过程,有兴趣的话,你可以自己琢磨一下哦。
这二叉堆还真有点意思,那么怎么用代码来实现呢?
3.3.3 二叉堆的代码实现
在展示代码之前,我们还需要明确一点:二叉堆虽然是一个完全二叉树,但它的存储方式并不是链式存储,而是顺序存储。换句话说,二叉堆的所有节点都存储在数组中。
在数组中,在没有左、右指针的情况下,如何定位一个父节点的左孩子和右孩子呢?
像上图那样,可以依靠数组下标来计算。
假设父节点的下标是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. * @param array 待调整的堆
4. */
5. public static void upAdjust(int[] array) {
6. int childIndex = array.length-1;
7. int parentIndex = (childIndex-1)/2;
8. // temp 保存插入的叶子节点值,用于最后的赋值
9. int temp = array[childIndex];
10. while (childIndex > 0 && temp < array[parentIndex])
11. {
12. //无须真正交换,单向赋值即可
13. array[childIndex] = array[parentIndex];
14. childIndex = parentIndex;
15. parentIndex = (parentIndex-1) / 2;
16. }
17. array[childIndex] = temp;
18. }
19.
20.
21. /**
22. * “下沉”调整
23. * @param array 待调整的堆
24. * @param parentIndex 要“下沉”的父节点
25. * @param length 堆的有效大小
26. */
27. public static void downAdjust(int[] array, int parentIndex,
int length) {
28. // temp 保存父节点值,用于最后的赋值
29. int temp = array[parentIndex];
30. int childIndex = 2 * parentIndex + 1;
31. while (childIndex < length) {
32. // 如果有右孩子,且右孩子小于左孩子的值,则定位到右孩子
33. if (childIndex + 1 < length && array[childIndex + 1] <
array[childIndex]) {
34. childIndex++;
35. }
36. // 如果父节点小于任何一个孩子的值,则直接跳出
37. if (temp <= array[childIndex])
38. break;
39. //无须真正交换,单向赋值即可
40. array[parentIndex] = array[childIndex];
41. parentIndex = childIndex;
42. childIndex = 2 * childIndex + 1;
43. }
44. array[parentIndex] = temp;
45. }
46.
47. /**
48. * 构建堆
49. * @param array 待调整的堆
50. */
51. public static void buildHeap(int[] array) {
52. // 从最后一个非叶子节点开始,依次做“下沉”调整
53. for (int i = (array.length-2)/2; i>=0; i--) {
54. downAdjust(array, i, array.length);
55. }
56. }
57.
58. public static void main(String[] args) {
59. int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};
60. upAdjust(array);
61. System.out.println(Arrays.toString(array));
62.
63. array = new int[] {7,1,3,10,5,2,8,9,6};
64. buildHeap(array);
65. System.out.println(Arrays.toString(array));
66. }
代码中有一个优化的点,就是在父节点和孩子节点做连续交换时,并不一定要真的交换,只需要先把交换一方的值存入temp变量,做单向覆盖,循环结束后,再把temp的值存入交换后的最终位置即可。
咱们讲了这么多关于二叉堆的知识,二叉堆究竟有什么用处呢?
二叉堆是实现堆排序 及优先队列 的基础。关于这两者,我们会在后续的章节中详细介绍。