PriorityQueue源码分析

概述

PriorityQueue是一个具有优先级的队列，可根据实现Comparable定制优先级规则，底层的数据结构为堆，默认使用小根堆。

注

大根堆：在二叉树中，所有根节点大于子节点。

小根堆：在二叉树中，所有子节点大于根节点。

具体可参考下图所示

方法解析

• add&offer方法

  public boolean offer(E e) {
          if (e == null)
              throw new NullPointerException();
          modCount++;
          int i = size;
          //如果当前大小不够，扩容。
          if (i >= queue.length)
              grow(i + 1);
          //调整
          siftUp(i, e);
          size = i + 1;
          return true;
      }
  

  • 首先判断是否需要扩容，扩容实现与ArrayList一致，申请一个新的数组，并将数据复制到新数组

  • 调整堆结构。因为新加的数据会破坏堆结构，因此需要调整堆结构，具体实现如下：

     private static <T> void siftUpUsingComparator(
            int k, T x, Object[] es, Comparator<? super T> cmp) {
            while (k > 0) {
                //父节点=(nodeNo-1)/2
                int parent = (k - 1) >>> 1;
                Object e = es[parent];
                if (cmp.compare(x, (T) e) >= 0)
                    break;
                es[k] = e;
                k = parent;
            }
            es[k] = x;
        }
    

    调整的过程为** : 从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue[parent]为止。

    注意

    注意: 这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序

• element&peek

  获取队列第一个元素，获取根节点的数据。

   public E peek() {
          return (E) queue[0];
      }
  

• remove&poll

  public E poll() {
      if (size == 0)
          return null;
      int s = --size;
      modCount++;
      //0下标处的那个元素就是最小的那个
      E result = (E) queue[0];
      E x = (E) queue[s];
      queue[s] = null;
      if (s != 0)
          //调整
          siftDown(0, x);
      return result;
  }
  
  //siftDown()
  private void siftDown(int k, E x) {
      int half = size >>> 1;
      while (k < half) {
      	//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
          //左孩子 = parentNo*2+1
          //右孩子 = parentNo*2+2
          int child = (k << 1) + 1;
          Object c = queue[child];
          int right = child + 1;
          if (right < size &&
              comparator.compare((E) c, (E) queue[right]) > 0)
              c = queue[child = right];
          if (comparator.compare(x, (E) c) <= 0)
              break;
          //然后用c取代原来的值
          queue[k] = c;
          k = child;
      }
      queue[k] = x;
  }
  
  
  

  流程：将队列最后一个位置数据放到第一个位置，然后与左右孩子比较，直至找到自己的位置，满足堆结构为止。

总结

• PriorityQueue底层数据结构为堆，默认为小根堆，可继承Comparable实现自定义的权值排序规则。