文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【重学数据结构】堆 Heap - 最小堆&最大堆

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

作者头像
程序员三明治
发布于 2025-12-18 20:10:02
发布于 2025-12-18 20:10:02
1580
举报
文章被收录于专栏：码力up码力up

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

什么是堆？

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

堆的数据结构

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

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

手写实现堆

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

堆接口

代码语言：javascript
复制
public interface IHeap<E> {
    boolean add(E e);

    boolean offer(E e);

    E poll();

    E peek();
}

堆实现类包含属性

代码语言：javascript
复制
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];
    }
}

入堆操作

代码语言：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<Integer> {

    @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<Integer> {

    @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。

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

最小堆：任何一个父节点的值都小于或等于其子节点 最大堆：任何一个父节点的值都大于或等于其子节点

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除
heap
null
测试
队列
数据结构

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

heap
null
测试
队列
数据结构
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 什么是堆？
  • 堆的数据结构
  • 手写实现堆
    • 堆接口
    • 堆实现类包含属性
    • 入堆操作
    • 出堆操作
  • 最小堆实现
  • 最大堆实现
  • 常见问题
    • 堆的数据结构是什么样？
    • 堆的数据结构使用场景？
    • 堆的数据结构实现方式有哪些？
    • 最小堆和最大堆的区别是什么？
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论