聊聊 Java 数据结构与算法中的堆最小堆和最大堆

发表于:2022-9-07 09:28

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:小傅哥    来源:bugstack虫洞栈

#
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]
  本文内容不用于商业目的,如涉及知识产权问题,请权利人联系51Testing小编(021-64471599-8017),我们将立即处理
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号