跳至主要內容

PriorityQueue源码分析

xw大约 2 分钟java基础集合框架

概述

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实现自定义的权值排序规则。