• 技术文章 >Java >java教程

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

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

    php入门到就业线上直播课:进入学习

    推荐学习:《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张图表述。

    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]

    推荐学习:《java视频教程

    以上就是Java数据结构之最小堆和最大堆的原理及实现详解的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:脚本之家,如有侵犯,请联系admin@php.cn删除
    专题推荐:java
    上一篇:Java Web动态网站开发教程 下一篇:一起聊聊Java封装、继承、多态特性
    VIP课程(WEB全栈开发)

    相关文章推荐

    • ❤️‍🔥共22门课程,总价3725元,会员免费学• 实例详解JavaScript中使用toLocaleString数字格式化• Java基础学习之ArrayList类概述与常用方法• Java详细解析之Bean作用域• Java概念理解总结之多态• 使用javascript需要安装什么吗
    1/1

    PHP中文网