当前位置：首页 > ai >正文

【重学数据结构】堆 Heap - 最小堆最大堆

ai 2025/7/28 9:28:13

什么是堆？

堆的数据结构

手写实现堆

堆接口

堆实现类包含属性

入堆操作

出堆操作

最小堆实现

最大堆实现

常见问题

堆的数据结构是什么样？

堆的数据结构使用场景？

堆的数据结构实现方式有哪些？

最小堆和最大堆的区别是什么？

在 Java API 中最常用的是用于实现优先队列的二叉堆，它是由 JWJ Williams 在 1964 年引入的，作为堆排序算法的数据结构。

什么是堆？

堆是基于树的特殊的数据结构，它可以在数组上构建出树的结构体，并满足堆的属性。堆中某个节点的值总是不大于或者不小于父节点的值，并且堆是一棵完全二叉树

堆的数据结构

最小堆：每个父节点的值都小于自己子节点的值

最大堆：与最小堆的定义正好相反，每个父节点的值都大于自己子节点的值

手写实现堆

从对堆的数据结构介绍上可以看到，小堆和大堆的唯一区别仅是对元素的排序方式不同。所以也就是说在存放和获取元素的时候对元素的填充和摘除时，排序方式不同而已。

堆接口

public interface IHeap<E> {boolean add(E e);boolean offer(E e);E poll();E peek();
}

堆实现类包含属性

public class Heap<E> implements IHeap<E>{private Logger logger = LoggerFactory.getLogger(Heap.class);private static final int DEFAULT_INITIAL_CAPACITY = 11;private Object[] queue;private int size;public Heap() {queue = new Object[DEFAULT_INITIAL_CAPACITY];}
}

入堆操作

    @Overridepublic boolean add(E e) {offer(e);return true;}@Overridepublic boolean offer(E e) {if (e == null) {throw new NullPointerException();}int i = size;if (i >= queue.length) {grow(i + 1);}size = i + 1;if (i == 0) {queue[i] = e;} else {siftUp(i, e);}return true;}// 上浮操作private void siftUp(int k, E e) {logger.info("【入队】元素：{} 当前队列：{}", JSON.toJSONString(e), JSON.toJSONString(queue));while (k > 0) {// 获取父节点Idx，相当于除以2int parent = (k - 1) >>> 1;logger.info("【入队】寻找当前节点的父节点位置。k：{} parent：{}", k, parent);Object parentE = queue[parent];// 如果当前位置元素，大于父节点元素，则退出循环if (compareTo(e, (E) parentE) >= 0) {logger.info("【入队】值比对，父节点：{} 目标节点：{}", JSON.toJSONString(parentE), JSON.toJSONString(e));break;}// 相反父节点位置大于当前位置元素，则进行替换logger.info("【入队】替换过程，父子节点位置替换，继续循环。父节点值：{} 存放到位置：{}", JSON.toJSONString(parentE), k);queue[k] = parentE;k = parent;}queue[k] = e;logger.info("【入队】完成 Idx：{} Val：{} \r\n当前队列：{} \r\n", k, JSON.toJSONString(e), JSON.toJSONString(queue));}private void grow(int minCapacity) {int oldCapacity = queue.length;// 小于64时翻倍增长，否则增长50%int newCapacity = oldCapacity + (oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1);// 防止整数溢出，设置最大容量限制if (newCapacity - (Integer.MAX_VALUE - 8) > 0) {newCapacity = (minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : minCapacity;}queue = Arrays.copyOf(queue, newCapacity);}

以入堆元素2举例，如图所示上浮过程。

首先将元素2挂到队列尾部，之后通过 (k - 1) >>> 1 计算父节点位置，与对应元素进行比对和判断交换。

交换过程包括 2->6、2->5，以此交换结束后元素保存完毕。

出堆操作

@Override
public E poll() {if (size == 0) {return null;}E result = (E) queue[0];int s = --size;E e = (E) queue[s];queue[s] = null;if (s != 0) {siftDown(0, e);}return result;
}
// 下沉操作
private void siftDown(int k, E e) {// 找到非叶子结点的位置（因为只有非叶子节点才有左右子节点）int notLeaf = size >>> 1;while (k < notLeaf) {// 找到左子节点和右子节点，两个节点进行比较，找出最大的值int child = (k << 1) + 1;Object c = queue[child];int right = child + 1;// 左子节点与右子节点比较，取最小的节点if (right < size && compareTo((E) c, (E) queue[right]) > 0) {logger.info("【入队】左右子节点比对，获取最小值。left：{} right：{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));c = queue[child = right];}// 目标值与c比较，当目标值小于c值，退出循环。说明此时目标值所在位置适合，迁移完成。if (compareTo(e, (E) c) <= 0) {break;}// 目标值大于c值，位置替换，继续比较logger.info("【入队】替换过程，节点的值比对。上节点:{},下节点:{} 位置替换", JSON.toJSONString(e), JSON.toJSONString(c));queue[k] = c;k = child;}// 把目标值放到对应位置logger.info("【出队】替换结果，最终更换位置。Idx：{} Val：{}", k, JSON.toJSONString(e));queue[k] = e;
}@Override
public E peek() {return (size == 0) ? null : (E) queue[0];
}public int compareTo(E firstElement, E secondElement) {throw new RuntimeException("未实现 compareTo 方法");
}

下沉过程画图举例说明

最小堆实现

小堆是一个正序比对

public class MinHeap extends Heap<Integer> {@Overridepublic int compareTo(Integer firstElement, Integer secondElement) {return firstElement.compareTo(secondElement);}}

测试

public class HeapTest {private static  final Logger logger = LoggerFactory.getLogger(HeapTest.class);public static void main(String[] args) {System.out.println("测试最小堆");MinHeap heap = new MinHeap();// 存入元素heap.add(1);heap.add(3);heap.add(5);heap.add(11);heap.add(4);heap.add(6);heap.add(7);heap.add(12);heap.add(15);heap.add(10);heap.add(9);heap.add(8);// 弹出元素while (heap.peek() != null){logger.info("测试结果：{}", heap.poll());}}
}

测试结果

测试最小堆
10:30:59.242 [main] INFO heap.Heap - 【入队】元素：3 当前队列：[1,null,null,null,null,null,null,null,null,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：1 parent：0
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：1 目标节点：3
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：1 Val：3 
当前队列：[1,3,null,null,null,null,null,null,null,null,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：5 当前队列：[1,3,null,null,null,null,null,null,null,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：2 parent：0
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：1 目标节点：5
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：2 Val：5 
当前队列：[1,3,5,null,null,null,null,null,null,null,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：11 当前队列：[1,3,5,null,null,null,null,null,null,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：3 parent：1
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：3 目标节点：11
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：3 Val：11 
当前队列：[1,3,5,11,null,null,null,null,null,null,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：4 当前队列：[1,3,5,11,null,null,null,null,null,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：4 parent：1
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：3 目标节点：4
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：4 Val：4 
当前队列：[1,3,5,11,4,null,null,null,null,null,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：6 当前队列：[1,3,5,11,4,null,null,null,null,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：5 parent：2
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：5 目标节点：6
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：5 Val：6 
当前队列：[1,3,5,11,4,6,null,null,null,null,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：7 当前队列：[1,3,5,11,4,6,null,null,null,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：6 parent：2
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：5 目标节点：7
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：6 Val：7 
当前队列：[1,3,5,11,4,6,7,null,null,null,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：12 当前队列：[1,3,5,11,4,6,7,null,null,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：7 parent：3
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：11 目标节点：12
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：7 Val：12 
当前队列：[1,3,5,11,4,6,7,12,null,null,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：15 当前队列：[1,3,5,11,4,6,7,12,null,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：8 parent：3
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：11 目标节点：15
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：8 Val：15 
当前队列：[1,3,5,11,4,6,7,12,15,null,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：10 当前队列：[1,3,5,11,4,6,7,12,15,null,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：9 parent：4
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：4 目标节点：10
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：9 Val：10 
当前队列：[1,3,5,11,4,6,7,12,15,10,null] 10:30:59.242 [main] INFO heap.Heap - 【入队】元素：9 当前队列：[1,3,5,11,4,6,7,12,15,10,null]
10:30:59.242 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：10 parent：4
10:30:59.242 [main] INFO heap.Heap - 【入队】值比对，父节点：4 目标节点：9
10:30:59.242 [main] INFO heap.Heap - 【入队】完成 Idx：10 Val：9 
当前队列：[1,3,5,11,4,6,7,12,15,10,9] 10:30:59.247 [main] INFO heap.Heap - 【入队】元素：8 当前队列：[1,3,5,11,4,6,7,12,15,10,9,null,null,null,null,null,null,null,null,null,null,null,null,null]
10:30:59.247 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：11 parent：5
10:30:59.247 [main] INFO heap.Heap - 【入队】值比对，父节点：6 目标节点：8
10:30:59.247 [main] INFO heap.Heap - 【入队】完成 Idx：11 Val：8 
当前队列：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null] 10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:8,下节点:3 位置替换
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：11 right：4
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:8,下节点:4 位置替换
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：10 right：9
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：4 Val：8
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：1
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:9,下节点:4 位置替换
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：11 right：8
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:9,下节点:8 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：4 Val：9
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：3
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：8 right：5
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:10,下节点:5 位置替换
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:10,下节点:6 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：5 Val：10
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：4
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：8 right：6
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:15,下节点:6 位置替换
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：10 right：7
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:15,下节点:7 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：6 Val：15
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：5
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：8 right：7
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:12,下节点:7 位置替换
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:12,下节点:10 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：5 Val：12
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：6
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:15,下节点:8 位置替换
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：11 right：9
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:15,下节点:9 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：4 Val：15
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：7
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:12,下节点:9 位置替换
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:12,下节点:11 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：3 Val：12
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：8
10:30:59.247 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：11 right：10
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:15,下节点:10 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：2 Val：15
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：9
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:12,下节点:11 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：1 Val：12
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：10
10:30:59.247 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:15,下节点:12 位置替换
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：1 Val：15
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：11
10:30:59.247 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：0 Val：15
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：12
10:30:59.247 [main] INFO heap.HeapTest - 测试结果：15

最大堆实现

大堆是一个反序比对

public class MaxHeap extends Heap<Integer> {@Overridepublic int compareTo(Integer firstElement, Integer secondElement) {return secondElement.compareTo(firstElement);}}

测试

public class HeapTest {private static  final Logger logger = LoggerFactory.getLogger(HeapTest.class);public static void main(String[] args) {System.out.println("测试最大堆");MaxHeap heap = new MaxHeap();// 存入元素heap.add(1);heap.add(3);heap.add(5);heap.add(11);heap.add(4);heap.add(6);heap.add(7);heap.add(12);heap.add(15);heap.add(10);heap.add(9);heap.add(8);// 弹出元素while (heap.peek() != null){logger.info("测试结果：{}", heap.poll());}}
}

测试结果

C:\jdk1.8.0_101\bin\java.exe "-javaagent:D:\IDEA\idea2021\IntelliJ IDEA 2021.2.2\lib\idea_rt.jar=51713:D:\IDEA\idea2021\IntelliJ IDEA 2021.2.2\bin" -Dfile.encoding=UTF-8 -classpath C:\jdk1.8.0_101\jre\lib\charsets.jar;C:\jdk1.8.0_101\jre\lib\deploy.jar;C:\jdk1.8.0_101\jre\lib\ext\access-bridge-64.jar;C:\jdk1.8.0_101\jre\lib\ext\cldrdata.jar;C:\jdk1.8.0_101\jre\lib\ext\dnsns.jar;C:\jdk1.8.0_101\jre\lib\ext\jaccess.jar;C:\jdk1.8.0_101\jre\lib\ext\jfxrt.jar;C:\jdk1.8.0_101\jre\lib\ext\localedata.jar;C:\jdk1.8.0_101\jre\lib\ext\mysql-connector-java-8.0.29.jar;C:\jdk1.8.0_101\jre\lib\ext\nashorn.jar;C:\jdk1.8.0_101\jre\lib\ext\sunec.jar;C:\jdk1.8.0_101\jre\lib\ext\sunjce_provider.jar;C:\jdk1.8.0_101\jre\lib\ext\sunmscapi.jar;C:\jdk1.8.0_101\jre\lib\ext\sunpkcs11.jar;C:\jdk1.8.0_101\jre\lib\ext\zipfs.jar;C:\jdk1.8.0_101\jre\lib\javaws.jar;C:\jdk1.8.0_101\jre\lib\jce.jar;C:\jdk1.8.0_101\jre\lib\jfr.jar;C:\jdk1.8.0_101\jre\lib\jfxswt.jar;C:\jdk1.8.0_101\jre\lib\jsse.jar;C:\jdk1.8.0_101\jre\lib\management-agent.jar;C:\jdk1.8.0_101\jre\lib\plugin.jar;C:\jdk1.8.0_101\jre\lib\resources.jar;C:\jdk1.8.0_101\jre\lib\rt.jar;D:\IdeaProjects\java-algorithms\data-structure\target\classes;E:\repository\org\slf4j\slf4j-api\1.7.36\slf4j-api-1.7.36.jar;E:\repository\com\alibaba\fastjson\2.0.12\fastjson-2.0.12.jar;E:\repository\com\alibaba\fastjson2\fastjson2-extension\2.0.12\fastjson2-extension-2.0.12.jar;E:\repository\com\alibaba\fastjson2\fastjson2\2.0.12\fastjson2-2.0.12.jar;E:\repository\ch\qos\logback\logback-core\1.2.11\logback-core-1.2.11.jar;E:\repository\ch\qos\logback\logback-classic\1.2.11\logback-classic-1.2.11.jar heap.HeapTest
测试最大堆
10:41:33.975 [main] INFO heap.Heap - 【入队】元素：3 当前队列：[1,null,null,null,null,null,null,null,null,null,null]
10:41:33.983 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：1 parent：0
10:41:33.983 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：1 存放到位置：1
10:41:33.983 [main] INFO heap.Heap - 【入队】完成 Idx：0 Val：3 
当前队列：[3,1,null,null,null,null,null,null,null,null,null] 10:41:33.983 [main] INFO heap.Heap - 【入队】元素：5 当前队列：[3,1,null,null,null,null,null,null,null,null,null]
10:41:33.983 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：2 parent：0
10:41:33.983 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：3 存放到位置：2
10:41:33.983 [main] INFO heap.Heap - 【入队】完成 Idx：0 Val：5 
当前队列：[5,1,3,null,null,null,null,null,null,null,null] 10:41:33.983 [main] INFO heap.Heap - 【入队】元素：11 当前队列：[5,1,3,null,null,null,null,null,null,null,null]
10:41:33.983 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：3 parent：1
10:41:33.984 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：1 存放到位置：3
10:41:33.984 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：1 parent：0
10:41:33.984 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：5 存放到位置：1
10:41:33.984 [main] INFO heap.Heap - 【入队】完成 Idx：0 Val：11 
当前队列：[11,5,3,1,null,null,null,null,null,null,null] 10:41:33.984 [main] INFO heap.Heap - 【入队】元素：4 当前队列：[11,5,3,1,null,null,null,null,null,null,null]
10:41:33.984 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：4 parent：1
10:41:33.984 [main] INFO heap.Heap - 【入队】值比对，父节点：5 目标节点：4
10:41:33.984 [main] INFO heap.Heap - 【入队】完成 Idx：4 Val：4 
当前队列：[11,5,3,1,4,null,null,null,null,null,null] 10:41:33.985 [main] INFO heap.Heap - 【入队】元素：6 当前队列：[11,5,3,1,4,null,null,null,null,null,null]
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：5 parent：2
10:41:33.985 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：3 存放到位置：5
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：2 parent：0
10:41:33.985 [main] INFO heap.Heap - 【入队】值比对，父节点：11 目标节点：6
10:41:33.985 [main] INFO heap.Heap - 【入队】完成 Idx：2 Val：6 
当前队列：[11,5,6,1,4,3,null,null,null,null,null] 10:41:33.985 [main] INFO heap.Heap - 【入队】元素：7 当前队列：[11,5,6,1,4,3,null,null,null,null,null]
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：6 parent：2
10:41:33.985 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：6 存放到位置：6
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：2 parent：0
10:41:33.985 [main] INFO heap.Heap - 【入队】值比对，父节点：11 目标节点：7
10:41:33.985 [main] INFO heap.Heap - 【入队】完成 Idx：2 Val：7 
当前队列：[11,5,7,1,4,3,6,null,null,null,null] 10:41:33.985 [main] INFO heap.Heap - 【入队】元素：12 当前队列：[11,5,7,1,4,3,6,null,null,null,null]
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：7 parent：3
10:41:33.985 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：1 存放到位置：7
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：3 parent：1
10:41:33.985 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：5 存放到位置：3
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：1 parent：0
10:41:33.985 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：11 存放到位置：1
10:41:33.985 [main] INFO heap.Heap - 【入队】完成 Idx：0 Val：12 
当前队列：[12,11,7,5,4,3,6,1,null,null,null] 10:41:33.985 [main] INFO heap.Heap - 【入队】元素：15 当前队列：[12,11,7,5,4,3,6,1,null,null,null]
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：8 parent：3
10:41:33.985 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：5 存放到位置：8
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：3 parent：1
10:41:33.985 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：11 存放到位置：3
10:41:33.985 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：1 parent：0
10:41:33.985 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：12 存放到位置：1
10:41:33.986 [main] INFO heap.Heap - 【入队】完成 Idx：0 Val：15 
当前队列：[15,12,7,11,4,3,6,1,5,null,null] 10:41:33.986 [main] INFO heap.Heap - 【入队】元素：10 当前队列：[15,12,7,11,4,3,6,1,5,null,null]
10:41:33.986 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：9 parent：4
10:41:33.986 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：4 存放到位置：9
10:41:33.986 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：4 parent：1
10:41:33.986 [main] INFO heap.Heap - 【入队】值比对，父节点：12 目标节点：10
10:41:33.986 [main] INFO heap.Heap - 【入队】完成 Idx：4 Val：10 
当前队列：[15,12,7,11,10,3,6,1,5,4,null] 10:41:33.986 [main] INFO heap.Heap - 【入队】元素：9 当前队列：[15,12,7,11,10,3,6,1,5,4,null]
10:41:33.986 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：10 parent：4
10:41:33.986 [main] INFO heap.Heap - 【入队】值比对，父节点：10 目标节点：9
10:41:33.986 [main] INFO heap.Heap - 【入队】完成 Idx：10 Val：9 
当前队列：[15,12,7,11,10,3,6,1,5,4,9] 10:41:33.986 [main] INFO heap.Heap - 【入队】元素：8 当前队列：[15,12,7,11,10,3,6,1,5,4,9,null,null,null,null,null,null,null,null,null,null,null,null,null]
10:41:33.986 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：11 parent：5
10:41:33.986 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：3 存放到位置：11
10:41:33.986 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：5 parent：2
10:41:33.986 [main] INFO heap.Heap - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：7 存放到位置：5
10:41:33.986 [main] INFO heap.Heap - 【入队】寻找当前节点的父节点位置。k：2 parent：0
10:41:33.986 [main] INFO heap.Heap - 【入队】值比对，父节点：15 目标节点：8
10:41:33.986 [main] INFO heap.Heap - 【入队】完成 Idx：2 Val：8 
当前队列：[15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null,null,null,null,null,null] 10:41:33.986 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:3,下节点:12 位置替换
10:41:33.986 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:3,下节点:11 位置替换
10:41:33.986 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：1 right：5
10:41:33.986 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:3,下节点:5 位置替换
10:41:33.986 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：8 Val：3
10:41:33.987 [main] INFO heap.HeapTest - 测试结果：15
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:9,下节点:11 位置替换
10:41:33.987 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：5 right：10
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:9,下节点:10 位置替换
10:41:33.987 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：4 Val：9
10:41:33.987 [main] INFO heap.HeapTest - 测试结果：12
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:4,下节点:10 位置替换
10:41:33.987 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：5 right：9
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:4,下节点:9 位置替换
10:41:33.987 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：4 Val：4
10:41:33.987 [main] INFO heap.HeapTest - 测试结果：11
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:3,下节点:9 位置替换
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:3,下节点:5 位置替换
10:41:33.987 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：3 Val：3
10:41:33.987 [main] INFO heap.HeapTest - 测试结果：10
10:41:33.987 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：5 right：8
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:1,下节点:8 位置替换
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:1,下节点:7 位置替换
10:41:33.987 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：5 Val：1
10:41:33.987 [main] INFO heap.HeapTest - 测试结果：9
10:41:33.987 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：5 right：7
10:41:33.987 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:6,下节点:7 位置替换
10:41:33.987 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：2 Val：6
10:41:33.987 [main] INFO heap.HeapTest - 测试结果：8
10:41:33.987 [main] INFO heap.Heap - 【入队】左右子节点比对，获取最小值。left：5 right：6
10:41:33.988 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:1,下节点:6 位置替换
10:41:33.988 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：2 Val：1
10:41:33.988 [main] INFO heap.HeapTest - 测试结果：7
10:41:33.988 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:4,下节点:5 位置替换
10:41:33.988 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：1 Val：4
10:41:33.988 [main] INFO heap.HeapTest - 测试结果：6
10:41:33.988 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:3,下节点:4 位置替换
10:41:33.988 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：1 Val：3
10:41:33.988 [main] INFO heap.HeapTest - 测试结果：5
10:41:33.988 [main] INFO heap.Heap - 【入队】替换过程，节点的值比对。上节点:1,下节点:3 位置替换
10:41:33.988 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：1 Val：1
10:41:33.988 [main] INFO heap.HeapTest - 测试结果：4
10:41:33.988 [main] INFO heap.Heap - 【出队】替换结果，最终更换位置。Idx：0 Val：1
10:41:33.988 [main] INFO heap.HeapTest - 测试结果：3
10:41:33.988 [main] INFO heap.HeapTest - 测试结果：1Process finished with exit code 0