《Java 数据结构与算法》第6章：堆最小堆&最大堆-低调大师

《Java 数据结构与算法》第6章：堆最小堆&最大堆

2022-09-04 296

持续坚持原创输出，点击蓝字关注我吧

作者：小傅哥
博客：https://bugstack.cn

❝
沉淀、分享、成长，让自己和他人都能有所收获！😜
❞

一、前言
二、堆的数据结构
三、堆的代码实现

1. 实现介绍
2. 入堆实现
3. 出堆实现
4. 小堆实现
5. 大堆实现

四、常见面试题

一、前言

堆的历史

堆的数据结构有很多种体现形式，包括；2-3堆、B堆、斐波那契堆，而在 Java API 中最常用的是用于实现优先队列的二叉堆，它是由 JWJ Williams 在 1964 年引入的，作为堆排序算法的数据结构。另外在 Dijkstra 算法等几种高效的图算法中，堆也是非常重要的。

二、堆的数据结构

在计算机科学中，堆(heap) 的实现是一种基于树的特殊的数据结构，它可以在数组上构建出树的结构体，并满足堆的属性；

最小堆：如果 P 是 C 的一个父级节点，那么 P 的key(或value)应小于或等于 C 的对应值。

最大堆：与最小堆的定义正好相反，最大堆(max heap) , P 的key(或value)大于 C 的对应值。

三、堆的代码实现

1. 实现介绍

堆的实现在 Java API 中主要体现在延迟队列的实现二叉堆上，这里小傅哥单独把这部分代码拆分出来，了解下关于小堆和大堆的实现。

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

2. 入堆实现

堆的在存放元素时，以遵循它的特点，会在存放过程中，通过队尾元素向上比对迁移。

private void siftUpComparable(int k, E x) {
    logger.info("【入队】元素：{} 当前队列：{}", JSON.toJSONString(x), JSON.toJSONString(queue));
    while (k > 0) {
        // 获取父节点Idx，相当于除以2
        int parent = (k - 1) >>> 1;
        logger.info("【入队】寻找当前节点的父节点位置。k：{} parent：{}", k, parent);
        Object e = queue[parent];
        // 如果当前位置元素，大于父节点元素，则退出循环
        if (compareTo(x, (E) e) >= 0) {
            logger.info("【入队】值比对，父节点：{} 目标节点：{}", JSON.toJSONString(e), JSON.toJSONString(x));
            break;
        }
        // 相反父节点位置大于当前位置元素，则进行替换
        logger.info("【入队】替换过程，父子节点位置替换，继续循环。父节点值：{} 存放到位置：{}", JSON.toJSONString(e), k);
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
    logger.info("【入队】完成 Idx：{} Val：{} \r\n当前队列：{} \r\n", k, JSON.toJSONString(x), JSON.toJSONString(queue));
}

入堆的实现 add 方法最终会调用到 siftUpComparable 方法，进行排序的方式进行处理。而这个排序 compareTo 方法是由具体的 MinHeap、MaxHeap 来做实现。
以入堆元素2举例，如图所示入堆过程。

首先将元素2挂到队列尾部，之后通过 (k - 1) >>> 1 计算父节点位置，与对应元素进行比对和判断交换。
交换过程包括 2->6、2->5，以此交换结束后元素保存完毕。

3. 出堆实现

元素的出堆其实很简单，只要把根元素直接删除弹出即可。但剩余接下里的步骤才是复杂的，因为需要在根元素迁移走后，寻找另外的最小元素迁移到对头。这个过程与入堆正好相反，这是一个不断向下迁移的过程。

private void siftDownComparable(int k, E x) {
    // 先找出中间件节点
    int half = size >>> 1;
    while (k < half) {
        // 找到左子节点和右子节点，两个节点进行比较，找出最大的值
        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(x, (E) c) <= 0) {
            break;
        }
        // 目标值小于c值，位置替换，继续比较
        logger.info("【出队】替换过程，节点的值比对。上节点：{} 下节点：{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c));
        queue[k] = c;
        k = child;
    }
    // 把目标值放到对应位置
    logger.info("【出队】替换结果，最终更换位置。Idx：{} Val：{}", k, JSON.toJSONString(x));
    queue[k] = x;
}

不断地向下迁移元素。这个过程会比对左右子节点的值，找到最小的。所以整个过程会比入堆麻烦一些。

这里以弹出元素1举例，之后将堆尾元素替换到相应的位置。整个过程分为6张图表述。

图1到图2，找出根元素弹出。
图3到图4，将根元素向下迁移，与子元素比对，并替换位置。如果这个位置与8相比，小于8则继续向下迁移。
图4到图5，继续迁移，在原节点4的位置对应的两个子元素，都比8大，这个时候就可以停下来了。
图5到图6，更换元素位置，把队尾的元素替换到对应元素1向下迁移检测的位置。

4. 小堆实现

小堆是一个正序比对

public class MinHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return firstElement.compareTo(secondElement);
    }

}

测试

@Test
public void test_min_heap() {
    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());
    }
}

结果

17:21:30.053 [main] INFO queue.PriorityQueue - 【入队】元素：3 当前队列：[1,null,null,null,null,null,null,null,null,null,null]
17:21:30.055 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：1 parent：0
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：1 目标节点：3
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：1 Val：3 
当前队列：[1,3,null,null,null,null,null,null,null,null,null] 

17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】元素：5 当前队列：[1,3,null,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：2 parent：0
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：1 目标节点：5
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：2 Val：5 
当前队列：[1,3,5,null,null,null,null,null,null,null,null] 

17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】元素：11 当前队列：[1,3,5,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：3 parent：1
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：3 目标节点：11
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：3 Val：11 
当前队列：[1,3,5,11,null,null,null,null,null,null,null] 

17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】元素：4 当前队列：[1,3,5,11,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：4 parent：1
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：3 目标节点：4
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：4 Val：4 
当前队列：[1,3,5,11,4,null,null,null,null,null,null] 

17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】元素：6 当前队列：[1,3,5,11,4,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：5 parent：2
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：5 目标节点：6
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：5 Val：6 
当前队列：[1,3,5,11,4,6,null,null,null,null,null] 

17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】元素：7 当前队列：[1,3,5,11,4,6,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：6 parent：2
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：5 目标节点：7
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：6 Val：7 
当前队列：[1,3,5,11,4,6,7,null,null,null,null] 

17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】元素：12 当前队列：[1,3,5,11,4,6,7,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：7 parent：3
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：11 目标节点：12
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：7 Val：12 
当前队列：[1,3,5,11,4,6,7,12,null,null,null] 

17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】元素：15 当前队列：[1,3,5,11,4,6,7,12,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：8 parent：3
17:21:30.056 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：11 目标节点：15
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：8 Val：15 
当前队列：[1,3,5,11,4,6,7,12,15,null,null] 

17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】元素：10 当前队列：[1,3,5,11,4,6,7,12,15,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：9 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：4 目标节点：10
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：9 Val：10 
当前队列：[1,3,5,11,4,6,7,12,15,10,null] 

17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】元素：9 当前队列：[1,3,5,11,4,6,7,12,15,10,null]
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：10 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：4 目标节点：9
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：10 Val：9 
当前队列：[1,3,5,11,4,6,7,12,15,10,9] 

17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】元素：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]
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：11 parent：5
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：6 目标节点：8
17:21:30.057 [main] INFO queue.PriorityQueue - 【入队】完成 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] 

17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：1 下节点：3 位置替换
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：3 下节点：4 位置替换
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：10 right：9
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：4 Val：8
17:21:30.057 [main] INFO heap.__test__.HeapTest - 测试结果：1
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：3 下节点：4 位置替换
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：8
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：4 下节点：8 位置替换
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：4 Val：9
17:21:30.057 [main] INFO heap.__test__.HeapTest - 测试结果：3
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：8 right：5
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：4 下节点：5 位置替换
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：5 下节点：6 位置替换
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：5 Val：10
17:21:30.057 [main] INFO heap.__test__.HeapTest - 测试结果：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：8 right：6
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：5 下节点：6 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：10 right：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：6 下节点：7 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：6 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：5
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：8 right：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：6 下节点：7 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：7 下节点：10 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：5 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：6
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：7 下节点：8 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：8 下节点：9 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：4 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：8 下节点：9 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：11 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：3 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：8
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：10 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：2 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：10 下节点：11 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：12 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：11
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：0 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：15

Process finished with exit code 0

小堆就是一个正序的输出结果，从小到大的排序和输出。
小堆空间： [1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

5. 大堆实现

小堆是一个反序比对

public class MaxHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return secondElement.compareTo(firstElement);
    }

}

测试

@Test
public void test_max_heap() {
    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());
    }
}

结果

17:23:45.079 [main] INFO queue.PriorityQueue - 【入队】元素：3 当前队列：[1,null,null,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：1 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：1 存放到位置：1
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：0 Val：3 
当前队列：[3,1,null,null,null,null,null,null,null,null,null] 

17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】元素：5 当前队列：[3,1,null,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：2 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：3 存放到位置：2
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：0 Val：5 
当前队列：[5,1,3,null,null,null,null,null,null,null,null] 

17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】元素：11 当前队列：[5,1,3,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：3 parent：1
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：1 存放到位置：3
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：1 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：5 存放到位置：1
17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：0 Val：11 
当前队列：[11,5,3,1,null,null,null,null,null,null,null] 

17:23:45.081 [main] INFO queue.PriorityQueue - 【入队】元素：4 当前队列：[11,5,3,1,null,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：4 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：5 目标节点：4
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：4 Val：4 
当前队列：[11,5,3,1,4,null,null,null,null,null,null] 

17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】元素：6 当前队列：[11,5,3,1,4,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：5 parent：2
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：3 存放到位置：5
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：2 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：11 目标节点：6
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：2 Val：6 
当前队列：[11,5,6,1,4,3,null,null,null,null,null] 

17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】元素：7 当前队列：[11,5,6,1,4,3,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：6 parent：2
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：6 存放到位置：6
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：2 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：11 目标节点：7
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：2 Val：7 
当前队列：[11,5,7,1,4,3,6,null,null,null,null] 

17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】元素：12 当前队列：[11,5,7,1,4,3,6,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：7 parent：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：1 存放到位置：7
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：3 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：5 存放到位置：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：11 存放到位置：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：0 Val：12 
当前队列：[12,11,7,5,4,3,6,1,null,null,null] 

17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】元素：15 当前队列：[12,11,7,5,4,3,6,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：8 parent：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：5 存放到位置：8
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：3 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：11 存放到位置：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：12 存放到位置：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：0 Val：15 
当前队列：[15,12,7,11,4,3,6,1,5,null,null] 

17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】元素：10 当前队列：[15,12,7,11,4,3,6,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：9 parent：4
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：4 存放到位置：9
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：4 parent：1
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：12 目标节点：10
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：4 Val：10 
当前队列：[15,12,7,11,10,3,6,1,5,4,null] 

17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】元素：9 当前队列：[15,12,7,11,10,3,6,1,5,4,null]
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：10 parent：4
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：10 目标节点：9
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】完成 Idx：10 Val：9 
当前队列：[15,12,7,11,10,3,6,1,5,4,9] 

17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】元素：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]
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：11 parent：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：3 存放到位置：11
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：5 parent：2
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】替换过程，父子节点位置替换，继续循环。父节点值：7 存放到位置：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】寻找当前节点的父节点位置。k：2 parent：0
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】值比对，父节点：15 目标节点：8
17:23:45.083 [main] INFO queue.PriorityQueue - 【入队】完成 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] 

17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：15 下节点：12 位置替换
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：12 下节点：11 位置替换
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：1 right：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：5 位置替换
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：8 Val：3
17:23:45.083 [main] INFO heap.__test__.HeapTest - 测试结果：15
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：12 下节点：11 位置替换
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：5 right：10
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：10 位置替换
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：4 Val：9
17:23:45.083 [main] INFO heap.__test__.HeapTest - 测试结果：12
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：10 位置替换
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：5 right：9
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：10 下节点：9 位置替换
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：4 Val：4
17:23:45.083 [main] INFO heap.__test__.HeapTest - 测试结果：11
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：10 下节点：9 位置替换
17:23:45.083 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：5 位置替换
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：3 Val：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：10
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：5 right：8
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：8 位置替换
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：8 下节点：7 位置替换
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：5 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：9
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：5 right：7
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：8 下节点：7 位置替换
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：2 Val：6
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：8
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：5 right：6
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：7 下节点：6 位置替换
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：2 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：7
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：6 下节点：5 位置替换
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：4
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：6
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：5 下节点：4 位置替换
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：5
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：4 下节点：3 位置替换
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：4
17:23:45.084 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：0 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 测试结果：1

Process finished with exit code 0

大堆就是一个反序的输出结果，从大到小的排序和输出。
大堆空间： [15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null,null,null,null,null,null]

四、常见面试题

堆的数据结构是什么样？
堆的数据结构使用场景？
堆的数据结构实现方式有哪些？
最小堆和最大堆的区别是什么？
有了解斐波那契堆吗？

- END -

下方扫码关注公众号【bugstack虫洞栈】回复【星球】，加入小傅哥的【私有技术朋友圈】你将获得；分布式DDD抽奖、API网关、IM通信、手写Mybatis、手写Spring、面经手册等高质量大厂项目和技术小册/PDF等资料。更多介绍

公众号：bugstack虫洞栈

你好，我是小傅哥。一线互联网 java 工程师、T8架构师，开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言，也搞过C#、PHP，是一个技术活跃的折腾者。

本文分享自微信公众号 - bugstack虫洞栈（bugstack）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

微信关注我们

原文链接：https://my.oschina.net/itstack/blog/5573469

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

这一次，我们把AI自治数据库带到了世界人工智能大会上

9月3日，2022世界人工智能大会（WAIC）在上海圆满落幕。WAIC2022 秉持“智联世界”理念，通过线上线下联动的会展形式，汇聚顶级科学家、企业家、政府官员、专家学者、国际组织、投资人、创新团队一同探讨科技前沿话题，推动全球“共创、共建、共融、共治、共享、共赢”。 WAIC 是经国务院批准，由国家发展和改革委员会、工业和信息化部、科学技术部、国家互联网信息办公室、中国科学院、中国工程院、中国科学技术协会和上海市人民政府共同主办。大会始终坚持高端化、国际化、专业化、市场化、智能化的办会理念，逐步成长为全球人工智能领域最具影响力的行业盛会。腾讯云数据库技术负责人程彬受邀参加 WAIC 大会滴水湖 AI 开发者创新论坛《当数据库遇上 AI 专场》。在专场中，程彬基于腾讯云数据库在 AI 智能化的探索与实践，分享数据库与 AI 融合背后的技术关键点，为产业界提供前沿解决方案。程彬认为，随着数据库规模的快速增长，以及数字化转型深入，传统的运营服务模式，给云厂商和企业在可用性、成本、运营效率等方面带来新挑战。数据库需要进一步智能化技术升级，数据库的构建方法论从传统的软硬结合，升级到软件+...

2022-09-06

240

选择 Go 还是 Rust？CloudWeGo-Volo 基于 Rust 语言的探索实践

本文整理自 CloudWeGo 开源一周年技术沙龙活动中字节跳动基础架构服务框架资深研发工程师吴迪的演讲分享，技术沙龙主题为《字节高性能开源微服务框架：CloudWeGo》。本文将从以下三个方面介绍 CloudWeGo 开源的国内首个 Rust RPC 框架 Volo： CloudWeGo 选择 Rust 语言进行探索的原因；创建 RPC 框架 Volo 的原因； Rust 语言和 Go 语言如何选择。 CloudWeGo 选择 Rust 语言进行探索的原因 CloudWeGo 正式官宣新一代 Rust RPC 框架 Volo 开源！很多朋友会有疑问，CloudWeGo 为什么会选择 Rust 这门语言进行探索呢？本文首先介绍一下其中的原因。 Volo 开源官宣：https://mp.weixin.qq.com/s/XcceLyKxWOVtoMIJBuwXWQ Go 的代价深度优化困难 Volo 早期的团队成员来自于 Kitex 项目（CloudWeGo 开源的 Golang 微服务 RPC 框架）。当时我们投入了大量的时间和精力优化 Kitex 以及其他相关基础库的性能，最终却...

2022-09-07

422

发表评论

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。