一、前言

本文将详细为大家讲解关于堆这种数据结构。学了本章以后我们会发现，呃呵，原来...名字听起来高大上的数据结构也就那么回事。

后面会持续更新数据结构相关的博文。

数据结构专栏：https://www.cnblogs.com/hello-shf/category/1519192.html

git传送门：https://github.com/hello-shf/data-structure.git

二、堆

堆这种数据结构，有很多的实现，比如：最大堆，最小堆，斐波那锲堆，左派堆，斜堆等。从孩子节点的个数上还可以分为二叉堆，N叉堆等。本文我们从最大二叉堆堆入手看看堆究竟是什么高大上的东东。

2.1、什么是堆

我们先看看它的定义

1 堆是一种完全二叉树（不是平衡二叉树，也不是二分搜索树哦）

2 堆要求孩子节点要小于等于父亲节点（如果是最小堆则大于等于其父亲节点）

满足以上两点性质即可成为一棵合格的堆数据结构。我们解读一下上面的两点性质

1，堆是一种完全二叉树，关于完全二叉树，在我另一篇博客《二分搜索树》中有详细的介绍，要注意堆是一种建立在二叉树上的数据结构，不同于AVL或者红黑树是建立在二分搜索树上的数据结构。

2，堆要求孩子节点要大于等于父亲节点，该定义是针对的最大堆。对于最小堆，孩子节点小于或者等于其父亲节点。

如上所示，只有图1是合格的最大堆，图2不满足父节点大于或者等于孩子节点的性质。图3不满足完全二叉树的性质。

2.2、堆的存储结构

前面我们说堆是一个完全二叉树，其中一种在合适不过的存储方式就是数组。首先从下图看一下用数组表示堆的可行性。

看了上图，说明数组确实是可以表示一个二叉堆的。使用数组来存储堆的节点信息，有一种天然的优势那就是节省内存空间。因为数组占用的是连续的内存空间，相对来说对于散列存储的结构来说，数组可以节省连续的内存空间，不会将内存打乱。

接下来看看数组到二叉堆的下标表示。将数组的索引设为 i。则：

左孩子找父节点：parent（i）= （i - 1）/2。比如2元素的索引为5，其父亲节点4的下标parent（2）= （5 - 1）/2 = 2；

右孩子找父节点：parent（i）= （i-2）/ 2。比如0元素找父节点 （6-2）/2= 2；

其实可以将上面的两种方法合并成一个，即parent（i）= （i - 1）/2；从java语法出发大家可以发现，整数相除得到的就是省略了小数位的。所以。。。你懂得。

同理

父节点找左孩子：leftChild(i)= parent(i)* 2 + 1。

父节点找右孩子：rightChild(i) = parent(i)*2 + 2。

三、最大二叉堆的实现

3.1、构建基础代码

上面分析了数组作为堆存储结构的可行性分析。接下来我们通过数组构建一下堆的基础结构

1 /**

2 * 描述：最大堆

3 *

4 * @Author shf

5 * @Date 2019/7/29 10:13

6 * @Version V1.0

7 **/

8 public class MaxHeap> {

9 //使用数组存储

10 private Array data;

11 public MaxHeap(){

12 data = new Array<>();

13 }

14 public MaxHeap(int capacity){

15 data = new Array<>(capacity);

16 }

17 public int size(){

18 return this.data.getSize();

19 }

20 public boolean isEmpty(){

21 return this.data.isEmpty();

22 }

23

24 /**

25 * 根据当前节点索引 index 计算其父节点的 索引

26 * @param index

27 * @return

28 */

29 private int parent(int index) {

30 if(index ==0){

31 throw new IllegalArgumentException("该节点为根节点");

32 }

33 return (index - 1) / 2;//这里为什么不分左右？因为java中 / 运算符只保留整数位。

34 }

35

36 /**

37 * 返回索引为 index 节点的左孩子节点的索引

38 * @param index

39 * @return

40 */

41 private int leftChild(int index){

42 return index*2 + 1;

43 }

44

45 /**

46 * 返回索引为 index 节点的右孩子节点的索引

47 * @param index

48 * @return

49 */

50 private int rightChild(int index){

51 return index*2 + 2;

52 }

53 }

3.2、插入和上浮 sift up

向堆中插入元素意味着该堆的性质可能遭到破坏，所以这是如同向AVL中插入元素后需要再平衡是一个道理，需要调整堆中元素的位置，使之重新满足堆的性质。在最大二叉堆中，要堆化一个元素，需要向上查找，找到它的父节点，大于父节点则交换两个元素，重复该过程直到每个节点都满足堆的性质为止。这个过程我们称之为上浮操作。下面我们用图例描述一下这个过程：

如上图5所示，我们向该堆中插入一个元素15。在数组中位于数组尾部。

如图6所示，向上查找，发现15大于它的父节点，所以进行交换。

如图7所示，继续向上查找，发现仍大于其父节点14。继续交换。

然后还会继续向上查找，发现小于其父节点19，停止上浮操作。整个二叉堆通过上浮操作维持了其性质。上浮操作的时间复杂度为O(logn)

插入和上浮操作的代码实现很简单，如下所示。

1 /**

2 * 向堆中添加元素

3 * @param e

4 */

5 public void add(E e){

6 // 向数组尾部添加元素

7 this.data.addLast(e);

8 siftUp(data.getSize() - 1);

9 }

10

11 /**

12 * 上浮操作

13 * @param k

14 */

15 private void siftUp(int k) {

16 // 上浮，如果大于父节点，进行交换

17 while(k > 0 && get(k).compareTo(get(parent(k))) > 0){

18 data.swap(k, parent(k));

19 k = parent(k);

20 }

21 }

3.3、取出堆顶元素和下沉 sift down

上面我们介绍了插入和上浮操作，那删除和下沉操作将不再是什么难题。一般的如果我们取出堆顶元素，我们选择将该数组中的最后一个元素替换堆顶元素，返回堆顶元素，删除最后一个元素。然后再对该元素做下沉操作 sift down。接下来我们通过图示看看一下过程。

如上图8所示，将堆顶元素取出，然后让最后一个元素移动到堆顶位置。删除最后一个元素，这时得到图9的结果。

如图10，堆顶的9元素会分别和其左右孩子节点进行比较，选出较大的孩子节点和其进行交换。很明显右孩子17大于左孩子15。即和右孩子进行交换。

如图11，9节点继续下沉最终和其左孩子12交换后，再没有孩子节点。此次过程的下沉操作完成。下沉操作的时间复杂度为O(logn)

代码实现仍然是非常简单

1 /**

2 * 取出堆中最大元素

3 * 时间复杂度 O（logn）

4 * @return

5 */

6 public E extractMax(){

7 E ret = findMax();

8 this.data.swap(0, (data.getSize() - 1));

9 data.removeLast();

10 siftDown(0);

11 return ret;

12 }

13

14 /**

15 * 下沉操作

16 * 时间复杂度 O（logn）

17 * @param k

18 */

19 public void siftDown(int k){

20 while(leftChild(k) < data.getSize()){// 从左节点开始，如果左节点小于数组长度，就没有右节点了

21 int j = leftChild(k);

22 if(j + 1 < data.getSize() && get(j + 1).compareTo(get(j)) > 0){// 选举出左右节点最大的那个

23 j ++;

24 }

25 if(get(k).compareTo(get(j)) >= 0){// 如果当前节点大于左右子节点，循环结束

26 break;

27 }

28 data.swap(k, j);

29 k = j;

30 }

31 }

3.4、Replace和Heapify

Replace操作呢其实就是取出堆顶元素然后新插入一个元素。根据我们上面的总结，大家很容易想到。返回堆顶元素后，直接将该元素置于堆顶，然后再进行下沉操作即可。

1 /**

2 * 取出最大的元素，并替换成元素 e

3 * 时间复杂度 O（logn）

4 * @param e

5 * @return

6 */

7 public E replace(E e){

8 E ret = findMax();

9 data.set(0, e);

10 siftDown(0);

11 return ret;

12 }

Heapify操作就比较有意思了。Heapify本身的意思为“堆化”，那我们将什么进行堆化呢？根据其存储结构，我们可以将任意一个数组进行堆化。将一个数组堆化？what？一个个向最大二叉堆中插入不就行了？呃，如果这样的话，需要对每一个元素进行一次上浮时间复杂度为O(nlogn)。显然这样做的话，时间复杂度控制的不够理想。有没有更好的方法呢。既然这样说了，肯定是有的。思路就是将一个数组当成一个完全二叉树，然后从最后一个非叶子节点开始逐个对飞叶子节点进行下沉操作。如何找到最后一个非叶子节点呢？这也是二叉堆常问的一个问题。相信大家还记得前面我们说过parent(i) = (child(i)-1)/2。这个公式是不分左右节点的哦，自己可以用代码验证一下，在前面的parent()方法中也有注释解释了。那么最后一个非叶子节点其实就是 （(arr.size())/2 - 1）即可。

接下来我们通过图示描述一下这个过程，假如我们将如下数组进行堆化

第一步：转化为一棵完全二叉树，如图12所示。

第二步：找到最后一个非叶子节点，如图13所示。这里我们将还未调整的非叶子节点设为黄色，将即将要调整的置为绿色。调整完成的置为绿边圆。

第三步：下沉，非叶子节点和左右孩子进行比较，选出最大的孩子节点进行交换。交换结果如图14所示

第四步：找到下一个非叶子节点。

第五步：下沉。

第六步：找到下一个非叶子节点。

第七步：下沉。

第八步：找到下一个非叶子节点。

第九步：下沉。30节点下沉到56元素的位置，然后继续下沉，但是发现大于23，下沉结束。

第十步：找到下一个非叶子节点。

第十一步：下沉。对17节点进行下沉操作，直到其直到适合自己的位置。

Heapify的整个过程就完成了。时间复杂度控制在了O(n)。

代码实现非常的简单。

1 /**

2 * Heapify

3 * @param arr

4 */

5 public MaxHeap(E[] arr){

6 data = new Array<>(arr);

7 for(int i = parent(arr.length - 1); i >= 0; i --){

8 siftDown(i);

9 }

10 }

四、完整代码

1 /**

2 * 描述：最大堆

3 *

4 * @Author shf

5 * @Date 2019/7/29 10:13

6 * @Version V1.0

7 **/

8 public class MaxHeap> {

9 //使用数组存储

10 private Array data;

11 public MaxHeap(){

12 data = new Array<>();

13 }

14 public MaxHeap(int capacity){

15 data = new Array<>(capacity);

16 }

17

18 /**

19 * Heapify

20 * @param arr

21 */

22 public MaxHeap(E[] arr){

23 data = new Array<>(arr);

24 for(int i = parent(arr.length - 1); i >= 0; i --){

25 siftDown(i);

26 }

27 }

28 public int size(){

29 return this.data.getSize();

30 }

31 public boolean isEmpty(){

32 return this.data.isEmpty();

33 }

34

35 /**

36 * 根据当前节点索引 index 计算其父节点的 索引

37 * @param index

38 * @return

39 */

40 private int parent(int index) {

41 if(index ==0){

42 throw new IllegalArgumentException("该节点为根节点");

43 }

44 return (index - 1) / 2;//这里为什么不分左右？因为java中 / 运算符只保留整数位。

45 }

46

47 /**

48 * 返回索引为 index 节点的左孩子节点的索引

49 * @param index

50 * @return

51 */

52 private int leftChild(int index){

53 return index*2 + 1;

54 }

55

56 /**

57 * 返回索引为 index 节点的右孩子节点的索引

58 * @param index

59 * @return

60 */

61 private int rightChild(int index){

62 return index*2 + 2;

63 }

64

65 /**

66 * 向堆中添加元素

67 * 时间复杂度 O（logn）

68 * @param e

69 */

70 public void add(E e){

71 // 向数组尾部添加元素

72 this.data.addLast(e);

73 siftUp(data.getSize() - 1);

74 }

75

76 /**

77 * 上浮操作

78 * 时间复杂度 O（logn）

79 * @param k

80 */

81 private void siftUp(int k) {

82 // 上浮，如果大于父节点，进行交换

83 while(k > 0 && get(k).compareTo(get(parent(k))) > 0){

84 data.swap(k, parent(k));

85 k = parent(k);

86 }

87 }

88

89 /**

90 * 获取 index 索引位置的元素

91 * 时间复杂度 O（1）

92 * @param index

93 * @return

94 */

95 private E get(int index){

96 return this.data.get(index);

97 }

98

99 /**

100 * 查找堆中的最大元素

101 * 时间复杂度 O（1）

102 * @return

103 */

104 public E findMax(){

105 if(this.data.getSize() == 0){

106 throw new IllegalArgumentException("当前heap为空");

107 }

108 return this.data.get(0);

109 }

110

111 /**

112 * 取出堆中最大元素

113 * 时间复杂度 O（logn）

114 * @return

115 */

116 public E extractMax(){

117 E ret = findMax();

118 this.data.swap(0, (data.getSize() - 1));

119 data.removeLast();

120 siftDown(0);

121 return ret;

122 }

123

124 /**

125 * 下沉操作

126 * 时间复杂度 O（logn）

127 * @param k

128 */

129 public void siftDown(int k){

130 while(leftChild(k) < data.getSize()){// 从左节点开始，如果左节点小于数组长度，就没有右节点了

131 int j = leftChild(k);

132 if(j + 1 < data.getSize() && get(j + 1).compareTo(get(j)) > 0){// 选举出左右节点最大的那个

133 j ++;

134 }

135 if(get(k).compareTo(get(j)) >= 0){// 如果当前节点大于左右子节点，循环结束

136 break;

137 }

138 data.swap(k, j);

139 k = j;

140 }

141 }

142

143 /**

144 * 取出最大的元素，并替换成元素 e

145 * 时间复杂度 O（logn）

146 * @param e

147 * @return

148 */

149 public E replace(E e){

150 E ret = findMax();

151 data.set(0, e);

152 siftDown(0);

153 return ret;

154 }

155 }

如有错误的地方还请留言指正。

原创不易，转载请注明原文地址：https://www.cnblogs.com/hello-shf/p/11393655.html