数据结构之堆结构
“堆”是一种树形结构，我们可以理解为堆是利用完全二叉树(对一颗具有n个结点的二叉树按层序编号，如果编号为i(1≤i≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为为完全二叉树)的结构来维护一组数据，并在实现”优先队列”时使用。
优先队列也是一种数据结构。在优先队列中，数据可以按任意顺序添加。相反，在取出数据时，首先选择最小值。能够自由地添加数据并从最小值开始取出，这种定义为优先队列。
让我们看看堆的结构。作为堆的一个规则，子类数字总是大于等于其父类数字-最小堆(或者子类总是小于等于其父类-最大堆)，其实只有当堆是最大堆或者最小堆才是真正意义上的堆。从堆中取出数字时，从最上面的数字取出。在堆中，最小值保存在顶部位置。所以使用堆这种数据结构可以快速取出最小的数据，但是无法执行在树中间取出数据的操作。
堆用于如优先队列、戴克斯特拉算法和堆排序等。关于戴克斯特拉算法属于数据结构中的搜索查找的内容，是图表搜索的算法，老四后期会浅析，你也可以先参考一下维基百科的介绍:
数据结构”堆”的动态描述图示如下，包含堆在移除顶部元素之后如何进行重排序的介绍。感谢同事”菠菜”同学提供的参考动图。
内容来自软件算法动画图解，喜欢的请付费支持，侵删
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 |
package com.glorze.heap; /** * 堆结点，即堆的元素 * @ClassName HeapNode * @author: 高老四 * @since: 2018年11月28日 下午3:40:06 */ public class HeapNode { /** * 堆的结点值，元素值 */ private int key; public HeapNode(int key) { this.key = key; } public void setKey(int key) { this.key = key; } public int getKey() { return key; } @Override public String toString() { return "HeapNode [key=" + key + "]"; } } |
|
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 |
package com.glorze.heap; /** * Java模拟堆(最小堆) * @ClassName Heap * @author: 高老四 * @since: 2018年11月28日 下午3:43:21 */ public class Heap { /** * 堆结点数组，也可以直接使用Integer数组 */ private HeapNode[] heapArray; /** * 数组的最大容量 */ private int maxSize; /** * 当前的数组的元素数量 */ private int currentSize; public Heap(int maxSize) { this.maxSize = maxSize; heapArray = new HeapNode[maxSize]; currentSize = 0; } /** * 建堆/向堆的末尾插入元素 使用向上调整的机制，这样只需要跟父节点进行值比较，减少比较次数 * @Title: insertNode * @param key 插入的元素值 * @return boolean 是否插入成功 * @author: glorze.com * @since: 2018年11月28日 下午3:44:53 */ public boolean insertNode(int key) { if (maxSize == currentSize) { return false; } HeapNode newNode = new HeapNode(key); heapArray[currentSize] = newNode; adjustUp(currentSize); ++currentSize; return true; } /** * 插入到堆最末的结点进行向上调整 * @Title: adjustUp * @param index 索引 * @return void * @author: 高老四 * @since: 2018年11月28日 下午3:50:58 */ public void adjustUp(int index) { int parentIndex = (index - 1) / 2; while (parentIndex >= 0) { if (heapArray[index].getKey() < heapArray[parentIndex].getKey()) { HeapNode temp = heapArray[index]; heapArray[index] = heapArray[parentIndex]; heapArray[parentIndex] = temp; index = parentIndex; // 对当前值的下标和其父结点的下标更新 parentIndex = (index - 1) / 2; } else { return; } } return; } /** * 删除根节点后，重新构造堆，向下调整 * @Title: trickleDown * @param index 索引 * @return void * @author: glorze.com * @since: 2018年11月28日 下午4:00:16 */ public void adjustDown(int index) { int leftChild; int rightChild; HeapNode temp; while (index < currentSize && index >= 0) { leftChild = 2 * index + 1; rightChild = 2 * index + 2; // 如果左孩子不存在 if (leftChild >= currentSize) { return; } else if (rightChild >= currentSize) { // 如果左孩子存在，右孩子不存在 if (heapArray[leftChild].getKey() < heapArray[index].getKey()) { temp = heapArray[index]; heapArray[index] = heapArray[leftChild]; heapArray[leftChild] = temp; index = leftChild; } } else { // 如果左右孩子都存在 if (heapArray[leftChild].getKey() < heapArray[rightChild].getKey()) { if(heapArray[leftChild].getKey() < heapArray[index].getKey()) { temp = heapArray[index]; heapArray[index] = heapArray[leftChild]; heapArray[leftChild] = temp; index = leftChild; } } else { if(heapArray[rightChild].getKey() < heapArray[index].getKey()) { temp = heapArray[index]; heapArray[index] = heapArray[rightChild]; heapArray[rightChild] = temp; index = rightChild; } } } } } /** * 从顶级父节点删除元素，然后重新建堆 * 重新建堆时，最好将最后一个结点放到堆顶，对其向下进行调整 * @Title: deleteRootNode * @return boolean 是否删除成功 * @author: 高老四 * @since: 2018年11月28日 下午3:57:17 */ public boolean deleteRootNode() { if (currentSize == 0) { return false; } // 业务要求可以将删除的根节点返回 // HeapNode root = heapArray[0]; heapArray[0] = heapArray[--currentSize]; adjustDown(0); return true; } /** * 更新某一结点的值重新构造最小堆 * @Title: changeNodeKey * @param index 索引 * @param newKey 新值 * @return boolean * @author: glorze.com * @since: 2018年11月28日 下午4:21:57 */ public boolean changeNodeKey(int index， int newKey) { if (index < currentSize && index >= 0) { // 若新值比当前值小，说明要把新值结点向上调整 if (heapArray[index].getKey() > newKey) { heapArray[index].setKey(newKey); adjustUp(index); } else { // 若新值比当前值大，说明要把新值结点向下调整 heapArray[index].setKey(newKey); adjustDown(index); } return true; } return false; } /** * 结果展示 * @Title: displayHeap * @param desc 描述词 * @return void * @author: 高老四 * @since: 2018年11月28日 下午4:22:37 */ public void displayHeap(String desc) { System.out.println(desc); for (int i = 0; i < this.currentSize; i++) { System.out.print(" " + heapArray[i].getKey()); } System.out.println(); } public static void main(String[] args) { Heap heap = new Heap(20); heap.insertNode(28); heap.insertNode(59); heap.insertNode(71); heap.insertNode(57); heap.insertNode(83); heap.insertNode(78); heap.insertNode(48); heap.insertNode(4); heap.insertNode(52); heap.insertNode(57); heap.displayHeap("初始化建堆结果: "); heap.deleteRootNode(); heap.displayHeap("删除父节点结果: "); heap.changeNodeKey(4， 8); heap.displayHeap("改变结点结果: "); } } |
堆排序
说到堆就离不开堆排序，但是其实再说堆的时候基本上就已经算是再讲堆排序(最大堆，最小堆)了，唯一不同的是堆排序需要我们输出一个完全有序的序列，所以在初始建堆的基础之上还需要进行堆顶与堆最后一个元素进行交换位置的操作，是简单选择排序的改进排序算法。结合上述介绍堆结构我们再来总结一下堆以及堆排序的相关知识点:
- 堆排序是简单选择排序的改进，简单排序的代码可参考下方代码
- 堆的性质: 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆;每个结点的值都小于等于其左右孩子结点的值，称为小顶堆;既不是大顶堆也不是小顶堆不是完整意义上的堆结构
- 完全二叉树的特点:
— 叶子结点只能出现在最下两层
— 最下层的叶子一定集中在左部连续位置
— 倒数第二层，若有叶子结点，一定都在右部连续位置
— 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
— 同样结点数的二叉树，完全二叉树的深度最小 -
满二叉树: 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树
- 满二叉树的特点:
— 叶子结点只能出现在最下一层.出现在其它层就不可能达到平衡.
— 非叶子结点的度一定是2.否则就是缺胳膊少腿了
— 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多 - 堆排序的时间复杂度: O(nlogn)
简单选择排序
通过n-i次关键字间的比较，从n-i+1个记录中选出的关键字最小的记录，并和第i(1≤i≤n)个记录交换之。简单选择排序时间复杂度: O(n²)。
使用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 |
package com.glorze.sort; import java.util.Arrays; /** * 简单选择排序Java实现 * @ClassName SelectSort * @author: glorze.com * @since: 2018年11月30日 下午4:23:16 */ public class SelectSort { /** * 冒泡是每次都交换值 * 简单选择排序是先比较，找到最小的再交换 * @Title: selectSort * @param arr 待排序数组 * @return int[] 结果 * @author: 高老四 * @since: 2018年11月30日 下午4:23:32 */ public static int[] selectSort(int arr[]) { int i， j， min， temp; for (i = 0; i < arr.length; i++) { min = i; for (j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { min = j; } } if (i != min) { temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } return arr; } public static void main(String[] args) { int arr[] = { 1， 3， 5， 7， 9， 2， 4， 6， 8 }; arr = SelectSort.selectSort(arr); System.out.println("简单选择排序: " + Arrays.toString(arr)); } } |
堆排序动态描述图如下:
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 68 69 70 71 |
package com.glorze.heapsort; import java.util.Arrays; /** * Java实现堆排序 * @ClassName HeapSort * @author: 高老四 * @since: 2018年11月30日 下午1:51:31 */ public class HeapSort { /** * 堆排序 * 将待排序序列构成一个大顶堆 * @Title: heapSort * @param arr 要排序的集合 * @return int[] 排序结果 * @author: glorze.com * @since: 2018年11月30日 下午2:29:46 */ public static int[] heapSort(int[] arr) { int i， temp; int magicNum = 2; // 从 0 到 arr.length/2 ，这些都是有孩子的节点 for (i = arr.length / magicNum; i >= 0; i--) { heapAdjust(arr， i， arr.length - 1); } // 逐步将每个最大值的根节点与末尾元素交换，并且再调整为大顶堆 for (i = arr.length - 1; i > 0; i--) { temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapAdjust(arr， 0， i - 1); } return arr; } /** * 向下调整 * @Title: heapAdjust * @param arr 待排序数组 * @param s 第一个索引 * @param m 最后一个元素的索引 * @return void * @author: 高老四 * @since: 2018年11月30日 下午2:34:03 */ private static void heapAdjust(int[] arr， int s， int m) { int temp， j; temp = arr[s]; int magicNum = 2; for (j = magicNum * s; j <= m; j *= magicNum) { if (j < m && arr[j] < arr[j + 1]) { j++; } if (temp >= arr[j]) { break; } arr[s] = arr[j]; s = j; } arr[s] = temp; } public static void main(String[] args) { int[] arr = {21， 24， 56， 12， 97， 2， 51， 58， 44}; arr = HeapSort.heapSort(arr); System.out.println("堆排序结果: " + Arrays.toString(arr)); } } |
说得容易，但是初学者肯定理解起来还是需要多花时间理解一下，平时再多看看一些书籍里面的详解，加深一下印象。
更博不易，如果觉得文章对你有帮助并且有能力的老铁烦请赞助盒烟钱，点我去赞助。或者扫描文章下面的微信/支付宝二维码打赏任意金额，老四这里抱拳了。赞助时请备注姓名或者昵称，因为您的署名会出现在赞赏列表页面，您的赞赏钱财也会被用于小站的服务器运维上面，再次抱拳。
