(七) 数据结构 - 最大堆
最大堆
堆是一种数据结构，一种叫做完全二叉树的数据结构。排序根据“堆属性”，其决定了树中节点的位置。
堆的常用场景：
构建优先队列
支持堆排序
快速找出一个集合中的最小值（或者最大值）
二叉堆(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, 1000000);
Integer[] integers1 = SortTestHelper.generateRandomArray(10000, 0, 1000000);
Integer[] integers2 = SortTestHelper.generateRandomArray(100000, 0, 1000000);
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数据量为100000" + 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数据量为100000" + 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数据量为100000" + SortTestHelper.testSort(integers2, new QuickSortOptimize()));
System.out.println("------------------------------近乎有序的数组--------------------------------");
Integer[] integers00 = SortTestHelper.generateNearlyOrderedArray(100, 10);
Integer[] integers11 = SortTestHelper.generateNearlyOrderedArray(10000, 100);
Integer[] integers22 = SortTestHelper.generateNearlyOrderedArray(100000, 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数据量为100000" + 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数据量为100000" + 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数据量为100000" + SortTestHelper.testSort(integers22, new QuickSortOptimize()));
Integer[] integers000 = SortTestHelper.generateRandomArray(100, 0, 10);
Integer[] integers111 = SortTestHelper.generateRandomArray(10000, 0, 100);
Integer[] integers222 = SortTestHelper.generateRandomArray(100000, 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数据量为100000" + 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数据量为100000" + 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数据量为100000" + 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数据量为100000排序时长为: 0.05s
快速排序优化测试1数据量为99排序时长为: 0.0s
快速排序优化测试2数据量为10000排序时长为: 0.011s
快速排序优化测试3数据量为100000排序时长为: 0.089s
堆排序测试1数据量为99排序时长为: 0.0s
堆排序测试2数据量为10000排序时长为: 0.001s
堆排序测试3数据量为100000排序时长为: 0.024s
------------------------------近乎有序的数组--------------------------------
归并排序优化测试1数据量为100排序时长为: 0.0s
归并排序优化测试2数据量为10000排序时长为: 0.001s
归并排序优化测试3数据量为100000排序时长为: 0.013s
快速排序优化测试1数据量为100排序时长为: 0.0s
快速排序优化测试2数据量为10000排序时长为: 0.001s
快速排序优化测试3数据量为100000排序时长为: 0.016s
堆排序测试1数据量为100排序时长为: 0.0s
堆排序测试2数据量为10000排序时长为: 0.001s
堆排序测试3数据量为100000排序时长为: 0.012s
------------------------------大量重复的数组--------------------------------
归并排序优化测试1数据量为100排序时长为: 0.0s
归并排序优化测试2数据量为10000排序时长为: 0.002s
归并排序优化测试3数据量为100000排序时长为: 0.023s
快速排序优化测试1数据量为100排序时长为: 0.0s
快速排序优化测试2数据量为10000排序时长为: 0.001s
快速排序优化测试3数据量为100000排序时长为: 0.011s
堆排序测试1数据量为100排序时长为: 0.0s
堆排序测试2数据量为10000排序时长为: 0.0s
堆排序测试3数据量为100000排序时长为: 0.009s参考原文：https://blog.csdn.net/love905661433/article/details/82989404
正文到此结束
