在 Java API 中最常用的是用于实现优先队列的二叉堆，它是由 JWJ Williams 在 1964 年引入的，作为堆排序算法的数据结构。
什么是堆？堆是基于树的特殊的数据结构，它可以在数组上构建出树的结构体，并满足堆的属性。堆中某个节点的值总是不大于或者不小于父节点的值，并且堆是一棵完全二叉树
堆的数据结构最小堆：每个父节点的值都小于自己子节点的值
最大堆：与最小堆的定义正好相反，每个父节点的值都大于自己子节点的值
手写实现堆 从对堆的数据结构介绍上可以看到，小堆和大堆的唯一区别仅是对元素的排序方式不同。所以也就是说在存放和获取元素的时候对元素的填充和摘除时，排序方式不同而已。
堆接口 代码语言：javascript复制public interface IHeap
boolean add(E e);
boolean offer(E e);
E poll();
E peek();
}堆实现类包含属性 代码语言：javascript复制public class Heap
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];
}
} 入堆操作代码语言：javascript复制 @Override
public boolean add(E e) {
offer(e);
return true;
}
@Override
public 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，相当于除以2
int 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，以此交换结束后元素保存完毕。
出堆操作代码语言：javascript复制@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 方法");
}下沉过程画图举例说明
最小堆实现 小堆是一个正序比对
代码语言：javascript复制public class MinHeap extends Heap
@Override
public int compareTo(Integer firstElement, Integer secondElement) {
return firstElement.compareTo(secondElement);
}
}测试
代码语言：javascript复制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());
}
}
}测试结果
代码语言：javascript复制测试最小堆
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最大堆实现大堆是一个反序比对
代码语言：javascript复制public class MaxHeap extends Heap
@Override
public int compareTo(Integer firstElement, Integer secondElement) {
return secondElement.compareTo(firstElement);
}
}测试
代码语言：javascript复制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());
}
}
}测试结果
代码语言：javascript复制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 - 测试结果：1
Process finished with exit code 0常见问题 堆的数据结构是什么样？ 是一种基于树的特殊的数据结构，它可以在数组上构建出树的结构体，并满足堆的属性；
堆的数据结构使用场景？ 堆排序算法，TopN的场景题，以及优先级队列是采用最小堆的性质去做的
堆的数据结构实现方式有哪些？ 二叉堆使用数组存储，根节点索引为0，子节点n的索引为2n+1和2n+2。
最小堆和最大堆的区别是什么？最小堆：任何一个父节点的值都小于或等于其子节点
最大堆：任何一个父节点的值都大于或等于其子节点