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

2022-11-13 16:11:03 数据结构 详解 大堆

一、前言

堆的历史

堆的数据结构有很多种体现形式,包括;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数据结构 堆的资料请关注其它相关文章!

相关文章