堆的原理和实现
- 2019 年 10 月 3 日
- 筆記
一、前言
本文将详细为大家讲解关于堆这种数据结构。学了本章以后我们会发现，呃呵，原来…名字听起来高大上的数据结构也就那么回事。
后面会持续更新数据结构相关的博文。
数据结构专栏：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<E extends Comparable<E>> { 9 //使用数组存储 10 private Array<E> 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()-1)/2即可。
接下来我们通过图示描述一下这个过程，假如我们将如下数组进行堆化
第一步：转化为一棵完全二叉树，如图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<E extends Comparable<E>> { 9 //使用数组存储 10 private Array<E> 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
