社区
学习
工具库
AI工具
休闲
搜索
简体中文
目录
一、前言
二、堆的数据结构
三、堆的代码实现
1. 实现介绍
2. 入堆实现
3. 出堆实现
4. 小堆实现
5. 大堆实现
首页 Java java教程 Java数据结构之最小堆和最大堆的原理及实现详解

Java数据结构之最小堆和最大堆的原理及实现详解

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Sep 05, 2022 pm 05:30 PM
java

本篇文章给大家带来了关于java的相关知识，在计算机科学中，堆(heap) 的实现是一种基于树的特殊的数据结构，它可以在数组上构建出树的结构体，并满足堆的属性，下面就来聊聊Java数据结构中的堆，感兴趣的可以了解一下。

Java数据结构之最小堆和最大堆的原理及实现详解

推荐学习：《java视频教程》

一、前言

堆的历史

堆的数据结构有很多种体现形式，包括；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]

  • 小堆就是一个正序的输出结果，从小到大的排序和输出。
  • 小堆空间：[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]

推荐学习：《java视频教程》

以上是Java数据结构之最小堆和最大堆的原理及实现详解的详细内容。更多信息请关注PHP中文网其他相关文章！

本站声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

显示更多

热门文章

R.E.P.O.能量晶体解释及其做什么（黄色晶体）
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
1 周前 By DDD
R.E.P.O.如果您听不到任何人，如何修复音频
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
在哪里可以找到原子中的起重机控制钥匙卡
1 周前 By DDD
显示更多

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里
7416
15
CakePHP 教程
1359
52
steam的账户名称是什么格式
76
11
win11激活密钥永久
27
19
显示更多
Related knowledge
Java 中的平方根 Java 中的平方根 Aug 30, 2024 pm 04:26 PM

Java 中的平方根指南。下面我们分别通过例子和代码实现来讨论平方根在Java中的工作原理。

Java 中的完美数 Java 中的完美数 Aug 30, 2024 pm 04:28 PM

Java 完美数指南。这里我们讨论定义，如何在 Java 中检查完美数？，示例和代码实现。

Java 中的随机数生成器 Java 中的随机数生成器 Aug 30, 2024 pm 04:27 PM

Java 随机数生成器指南。在这里，我们通过示例讨论 Java 中的函数，并通过示例讨论两个不同的生成器。

Java 中的阿姆斯特朗数 Java 中的阿姆斯特朗数 Aug 30, 2024 pm 04:26 PM

Java 中的阿姆斯特朗数指南。这里我们讨论一下java中阿姆斯特朗数的介绍以及一些代码。

Java中的Weka Java中的Weka Aug 30, 2024 pm 04:28 PM

Java 版 Weka 指南。这里我们通过示例讨论简介、如何使用weka java、平台类型和优点。

Java 中的史密斯数 Java 中的史密斯数 Aug 30, 2024 pm 04:28 PM

Java 史密斯数指南。这里我们讨论定义，如何在Java中检查史密斯号？带有代码实现的示例。

Java Spring 面试题 Java Spring 面试题 Aug 30, 2024 pm 04:29 PM

在本文中，我们保留了最常被问到的 Java Spring 面试问题及其详细答案。这样你就可以顺利通过面试。

突破或从Java 8流返回？ 突破或从Java 8流返回？ Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API，提供了一种强大且表达力丰富的处理数据集合的方式。然而，使用Stream时，一个常见问题是：如何从forEach操作中中断或返回？ 传统循环允许提前中断或返回，但Stream的forEach方法并不直接支持这种方式。本文将解释原因，并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读： Java Stream API改进 理解Stream forEach forEach方法是一个终端操作，它对Stream中的每个元素执行一个操作。它的设计意图是处

See all articles