大家好，欢迎来到IT知识分享网。
最大堆
堆是一种数据结构，一种叫做完全二叉树的数据结构。排序根据“堆属性”，其决定了树中节点的位置。
堆的常用场景：
- 构建优先队列
- 支持堆排序
- 快速找出一个集合中的最小值（或者最大值）
二叉堆(Binary Heap)
- 二叉堆是一颗完全二叉树
- 堆中某个节点的值总是大于等于(或小于等于)其子节点, 对应的就是最大堆和最小堆
可以用数组存储二叉堆, 数组下标以1开始,可以如下展示 :
数组从0开始, 展示如下 :
常见操作
添加元素
- 在数组的最后一个位置添加一个新元素
- 新的元素进行上浮(Sift Up), 上浮操作如下图:
取出元素
堆每次只能取出最大的元素, 具体取出元素的步骤如下 :
- 将堆的根节点与最后一个元素交换位置
- 删除最后的一个元素, 此时最后一个元素位于根节点
- 如果左右子节点不小于现在的根节点, 则将现有根节点和左右子节点中较大的那个交换位置
- 重复上一步, 直到不再需要最后的那个节点找到它应该存放的位置, 示意图如下
替换元素
取出堆中的最大元素, 再放入新元素, 步骤如下:
- 直接将堆顶元素替换成新元素
- 对新元素执行Sift Down操作
将任意数组整理成堆(heapify)
- 首先将数组当成一个完全二叉树
- 找到最后一个非叶子节点, 方法是根据最后一个元素计算其父节点
- 从最后一个非叶子节点之前的节点都执行Sift Down操作
最大堆代码实现
最大堆：
package com.paal.demo.heap; / * <p/> * <li>title: 最大堆</li> * <li>@author: li.pan</li> * <li>Date: 2019/12/24 9:01 下午</li> * <li>Version: V1.0</li> * <li>Description: * <p> * 数组下标以1开始时,父节点parent(i)=i/2, left child (i)= 2*i, right child = 2*i +1 * <p> * 在堆的有关操作中，需要比较堆中元素的大小，所以E需要extends Comparable接口 * <p> * </li> */ public class MaxHeap<E extends Comparable> { protected E[] data; protected int count; protected int capacity; / * 构造函数, 构造一个空堆, 可容纳capacity个元素 * * @param capacity */ public MaxHeap(int capacity) { data = (E[]) new Comparable[capacity + 1]; count = 0; this.capacity = capacity; } / * 构造函数, 通过一个给定数组创建一个最大堆 * Heapify方式将集合中的元素添加到最大堆中 该构造堆的过程, 时间复杂度为O(n) * * @param arr */ public MaxHeap(E[] arr) { int n = arr.length; data = (E[]) new Comparable[n + 1]; capacity = n; for (int i = 0; i < n; i++) data[i + 1] = arr[i]; count = n; for (int i = count / 2; i >= 1; i--) shiftDown(i); } / * 返回堆中元素个数 * * @return */ public int size() { return count; } / * 返回堆是否为空 * * @return */ public boolean isEmpty() { return count == 0; } / * 像最大堆中插入一个新的元素 * * @param item 元素E */ public void insert(E item) { assert count + 1 <= capacity; data[count + 1] = item; count++; shiftUp(count); } / * 从最大堆中取出堆顶元素, 即堆中所存储的最大数据 * * @return */ public E extractMax() { assert count > 0; //获取最大值 E ret = data[1]; //将根结点和最后一个叶子节点交换位置,即用最后一个叶子结点替换根结点 swap(1, count); //删除最后一个节点 count--; // 根结点下沉 shiftDown(1); return ret; } / * 节点上浮 * * @param k 索引 */ private void shiftUp(int k) { //不是根结点,且当前节点大于父节点时,和父节点交换位置 while (k > 1 && data[k / 2].compareTo(data[k]) < 0) { swap(k, k / 2); k /= 2; } } / * 节点下沉 * * @param k */ private void shiftDown(int k) { // 防止数组越界 while (2 * k <= count) { int j = 2 * k; // 在此轮循环中,data[k]和data[j]交换位置 // data[j] 是 data[2*k]和data[2*k+1]中的最大值 if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0) j++; if (data[k].compareTo(data[j]) >= 0) break; swap(k, j); k = j; } } / * 获取最大堆中的堆顶元素 * * @return */ public E getMax() { assert (count > 0); return data[1]; } / * 交换堆中索引为i和j的两个元素 * * @param i 索引i * @param j 索引j */ private void swap(int i, int j) { E t = data[i]; data[i] = data[j]; data[j] = t; } }打印最大堆工具类：
package com.paal.demo.heap; / * <p/> * <li>title: 打印最大堆</li> * <li>@author: li.pan</li> * <li>Date: 2019/12/28 18:01 下午</li> * <li>Version: V1.0</li> * <li>Description: * <p> * PrintableMaxHeap只能处理整数信息，所以继承的是MaxHeap<Comparable<Integer>> * <p> * </li> */ public class PrintableMaxHeap extends MaxHeap<Comparable<Integer>> { public PrintableMaxHeap(int capacity) { super(capacity); } public PrintableMaxHeap(Integer[] e) { super(e); } / * 以树状打印整个堆结构 */ public void treePrint() { if (size() >= 100) { System.out.println("This print function can only work for less than 100 integer"); return; } System.out.println("The max heap size is: " + size()); System.out.println("最大堆图示结构如下: "); System.out.println(); System.out.println(); int n = size(); int maxLevel = 0; int numberPerLevel = 1; while (n > 0) { maxLevel += 1; n -= numberPerLevel; numberPerLevel *= 2; } int maxLevelNumber = (int) Math.pow(2, maxLevel - 1); int curTreeMaxLevelNumber = maxLevelNumber; int index = 1; for (int level = 0; level < maxLevel; level++) { String line1 = new String(new char[maxLevelNumber * 3 - 1]).replace('\0', ' '); int curLevelNumber = Math.min(count - (int) Math.pow(2, level) + 1, (int) Math.pow(2, level)); boolean isLeft = true; for (int indexCurLevel = 0; indexCurLevel < curLevelNumber; index++, indexCurLevel++) { line1 = putNumberInLine((Integer) data[index], line1, indexCurLevel, curTreeMaxLevelNumber * 3 - 1, isLeft); isLeft = !isLeft; } System.out.println(line1); if (level == maxLevel - 1) break; String line2 = new String(new char[maxLevelNumber * 3 - 1]).replace('\0', ' '); for (int indexCurLevel = 0; indexCurLevel < curLevelNumber; indexCurLevel++) line2 = putBranchInLine(line2, indexCurLevel, curTreeMaxLevelNumber * 3 - 1); System.out.println(line2); curTreeMaxLevelNumber /= 2; } } private String putNumberInLine(Integer num, String line, int indexCurLevel, int curTreeWidth, boolean isLeft) { int subTreeWidth = (curTreeWidth - 1) / 2; int offset = indexCurLevel * (curTreeWidth + 1) + subTreeWidth; assert offset + 1 < line.length(); if (num >= 10) line = line.substring(0, offset + 0) + num.toString() + line.substring(offset + 2); else { if (isLeft) line = line.substring(0, offset + 0) + num.toString() + line.substring(offset + 1); else line = line.substring(0, offset + 1) + num.toString() + line.substring(offset + 2); } return line; } private String putBranchInLine(String line, int indexCurLevel, int curTreeWidth) { int subTreeWidth = (curTreeWidth - 1) / 2; int subSubTreeWidth = (subTreeWidth - 1) / 2; int offsetLeft = indexCurLevel * (curTreeWidth + 1) + subSubTreeWidth; assert offsetLeft + 1 < line.length(); int offsetRight = indexCurLevel * (curTreeWidth + 1) + subTreeWidth + 1 + subSubTreeWidth; assert offsetRight < line.length(); line = line.substring(0, offsetLeft + 1) + "/" + line.substring(offsetLeft + 2); line = line.substring(0, offsetRight) + "\\" + line.substring(offsetRight + 1); return line; } // 测试 PrintableMaxHeap // public static void main(String[] args) { // // PrintableMaxHeap maxHeap = new PrintableMaxHeap(100); // int N = 99; // 堆中元素个数 // int M = 100; // 堆中元素取值范围[0, M) // for (int i = 0; i < N; i++) // maxHeap.insert(new Integer((int) (Math.random() * M))); // maxHeap.treePrint(); // // } }测试方法：
/ * 堆排序测试 */ @Test public void heapSortTest() { Integer[] integers = SortTestHelper.generateRandomArray(50, 0, 100); Integer[] integers0 = SortTestHelper.generateRandomArray(99, 0, ); Integer[] integers1 = SortTestHelper.generateRandomArray(10000, 0, ); Integer[] integers2 = SortTestHelper.generateRandomArray(, 0, ); System.out.println("------------------------------最大堆结构--------------------------------"); new PrintableMaxHeap(integers).treePrint(); System.out.println("------------------------------随机数组--------------------------------"); System.out.println("归并排序优化测试1数据量为99" + SortTestHelper.testSort(integers0, new MergeSortOptimize())); System.out.println("归并排序优化测试2数据量为10000" + SortTestHelper.testSort(integers1, new MergeSortOptimize())); System.out.println("归并排序优化测试3数据量为" + SortTestHelper.testSort(integers2, new MergeSortOptimize())); System.out.println("快速排序优化测试1数据量为99" + SortTestHelper.testSort(integers0, new QuickSortOptimize())); System.out.println("快速排序优化测试2数据量为10000" + SortTestHelper.testSort(integers1, new QuickSortOptimize())); System.out.println("快速排序优化测试3数据量为" + SortTestHelper.testSort(integers2, new QuickSortOptimize())); System.out.println("堆排序测试1数据量为99" + SortTestHelper.testSort(integers0, new HeapSort())); System.out.println("堆排序测试2数据量为10000" + SortTestHelper.testSort(integers1, new QuickSortOptimize())); System.out.println("堆排序测试3数据量为" + SortTestHelper.testSort(integers2, new QuickSortOptimize())); System.out.println("------------------------------近乎有序的数组--------------------------------"); Integer[] integers00 = SortTestHelper.generateNearlyOrderedArray(100, 10); Integer[] integers11 = SortTestHelper.generateNearlyOrderedArray(10000, 100); Integer[] integers22 = SortTestHelper.generateNearlyOrderedArray(, 1000); System.out.println("归并排序优化测试1数据量为100" + SortTestHelper.testSort(integers00, new MergeSortOptimize())); System.out.println("归并排序优化测试2数据量为10000" + SortTestHelper.testSort(integers11, new MergeSortOptimize())); System.out.println("归并排序优化测试3数据量为" + SortTestHelper.testSort(integers22, new MergeSortOptimize())); System.out.println("快速排序优化测试1数据量为100" + SortTestHelper.testSort(integers00, new QuickSortOptimize())); System.out.println("快速排序优化测试2数据量为10000" + SortTestHelper.testSort(integers11, new QuickSortOptimize())); System.out.println("快速排序优化测试3数据量为" + SortTestHelper.testSort(integers22, new QuickSortOptimize())); System.out.println("堆排序测试1数据量为100" + SortTestHelper.testSort(integers00, new HeapSort())); System.out.println("堆排序测试2数据量为10000" + SortTestHelper.testSort(integers11, new QuickSortOptimize())); System.out.println("堆排序测试3数据量为" + SortTestHelper.testSort(integers22, new QuickSortOptimize())); Integer[] integers000 = SortTestHelper.generateRandomArray(100, 0, 10); Integer[] integers111 = SortTestHelper.generateRandomArray(10000, 0, 100); Integer[] integers222 = SortTestHelper.generateRandomArray(, 0, 1000); System.out.println("------------------------------大量重复的数组--------------------------------"); System.out.println("归并排序优化测试1数据量为100" + SortTestHelper.testSort(integers000, new MergeSortOptimize())); System.out.println("归并排序优化测试2数据量为10000" + SortTestHelper.testSort(integers111, new MergeSortOptimize())); System.out.println("归并排序优化测试3数据量为" + SortTestHelper.testSort(integers222, new MergeSortOptimize())); System.out.println("快速排序优化测试1数据量为100" + SortTestHelper.testSort(integers000, new QuickSortOptimize())); System.out.println("快速排序优化测试2数据量为10000" + SortTestHelper.testSort(integers111, new QuickSortOptimize())); System.out.println("快速排序优化测试3数据量为" + SortTestHelper.testSort(integers222, new QuickSortOptimize())); System.out.println("堆排序测试1数据量为100" + SortTestHelper.testSort(integers000, new HeapSort())); System.out.println("堆排序测试2数据量为10000" + SortTestHelper.testSort(integers111, new QuickSortOptimize())); System.out.println("堆排序测试3数据量为" + SortTestHelper.testSort(integers222, new QuickSortOptimize())); }运行结果：
------------------------------最大堆结构-------------------------------- The max heap size is: 50 最大堆图示结构如下: 99 / \ 99 98 / \ / \ 98 88 94 45 / \ / \ / \ / \ 95 86 84 85 78 87 32 25 / \ / \ / \ / \ / \ / \ / \ / \ 92 85 53 36 81 53 30 47 60 35 65 70 15 6 12 12 / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ 78 63 35 28 12 19 17 17 68 57 36 38 23 9 12 5 37 21 17 ------------------------------随机数组-------------------------------- 归并排序优化测试1数据量为99排序时长为: 0.0s 归并排序优化测试2数据量为10000排序时长为: 0.007s 归并排序优化测试3数据量为排序时长为: 0.05s 快速排序优化测试1数据量为99排序时长为: 0.0s 快速排序优化测试2数据量为10000排序时长为: 0.011s 快速排序优化测试3数据量为排序时长为: 0.089s 堆排序测试1数据量为99排序时长为: 0.0s 堆排序测试2数据量为10000排序时长为: 0.001s 堆排序测试3数据量为排序时长为: 0.024s ------------------------------近乎有序的数组-------------------------------- 归并排序优化测试1数据量为100排序时长为: 0.0s 归并排序优化测试2数据量为10000排序时长为: 0.001s 归并排序优化测试3数据量为排序时长为: 0.013s 快速排序优化测试1数据量为100排序时长为: 0.0s 快速排序优化测试2数据量为10000排序时长为: 0.001s 快速排序优化测试3数据量为排序时长为: 0.016s 堆排序测试1数据量为100排序时长为: 0.0s 堆排序测试2数据量为10000排序时长为: 0.001s 堆排序测试3数据量为排序时长为: 0.012s ------------------------------大量重复的数组-------------------------------- 归并排序优化测试1数据量为100排序时长为: 0.0s 归并排序优化测试2数据量为10000排序时长为: 0.002s 归并排序优化测试3数据量为排序时长为: 0.023s 快速排序优化测试1数据量为100排序时长为: 0.0s 快速排序优化测试2数据量为10000排序时长为: 0.001s 快速排序优化测试3数据量为排序时长为: 0.011s 堆排序测试1数据量为100排序时长为: 0.0s 堆排序测试2数据量为10000排序时长为: 0.0s 堆排序测试3数据量为排序时长为: 0.009s参考原文：(七) 数据结构 – 最大堆
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/114543.html
