文章目录

• 1、概述
• 2、入队分析
• 3、出队分析
• 4、总结

1、概述

PriorityQueue 称为优先队列，也是一种特殊的有序队列。为什么特殊呢？

因为其内部使用 Object[] 数组来存储数据，整个数组从0 ~ 最后一个并不是有序排放的，但是出队的时候数据又是从小到大有序的。

来看个例子：

public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue();
        Random random = new Random();
        final int count = 7;
        System.out.print("入队开始：");
        for (int i = 0; i < count; i++){
            int number = random.nextInt(100);
            System.out.print(number + "，");
            queue.offer(number);
        }
        System.out.println();
        System.out.print("队列数组：");
        for (Object o : queue.toArray()) {
            System.out.print(o + "，");
        }
        System.out.println();
        System.out.print("出队开始：");
        for (int i = 0; i < count; i++) {
            Object number = queue.poll();
            System.out.print(number + "，");
        }
    }
}

输出结果如下，如上面所说，数组的内容不是按顺序的，但是出队是从小到大有序的：

入队开始：86，13，66，49，82，37，87，
队列数组：13，49，37，86，82，66，87，
出队开始：13，37，49，66，82，86，87，

2、入队分析

offer 源码：

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

offer 流程图：

上面最后一步，特殊的入队逻辑 具体是怎样的，咱继续分析一下。

先上源码：

	//k：数组第一个空位的索引值，例如：当前已经填充了2个元素，再次执行到这里k就是2
	//x：准备入队的对象
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

这段代码的大致逻辑是：

• 查到当前入队对象（x）的父对象（e），这里的父对象不是上一个元素，也是类似树结构的父对象，下面会讲到
• 如果 x >= e，则将 x 放到数组下标位置 k，执行结束
• 如果 x < e，把 e 放到数组下标位置 k，同时把原下标赋给 k，继续执行第一步

这里用到移位运算法，顺便讲解一下

int parent = (k - 1) >>> 1：获取当前元素的父级，>>> 1 表示将二进制值右移1位，左边补0

举几个例子：

十进制0，对应二进制0000，右移1位仍然是0000，结果是0
十进制1，对应二进制0001，右移1位变成0000，结果是0
十进制2，对应二进制0010，右移1位变成0001，结果是1
十进制3，对应二进制0011，右移1位变成0001，结果是1
十进制4，对应二进制0100，右移1位变成0010，结果是2
十进制5，对应二进制0101，右移1位变成0010，结果是2

用一个流程图表示就是这样：

分解步骤，就以上面的入队顺序为例子（86，13，66，49，82，37，87）：

第1个对象，x = 86，直接放到数组第0位

第2个对象，x = 13

• k = 1，parent = 0，因为 13 < 86，所以执行queue[1] = 86
• 然后执行 k = parent，也就是 k = 0，所以执行 queue[0] = 13
  

第3个对象，x = 66

• k=2，parent=0，因为 66 > 13，所以直接放在 k 位置上
  

第4个对象，x = 49

• k=3，parent=1，因为 49 < 86，所以 86 要往下移
  
• 因为此时 49 > 13，所以不需要继续移位

第5个对象，x = 82

• k=4，parent=1，因为 82 > 49，所以直接赋值
  

第6个对象，x = 37

• k=5，parent=2，因为 37 < 66，所以 66 需要下移
  
• 因为37 > 13，所以不需要继续移位

第7个对象 x = 87

• k=6，parent=2，因为 87 > 37，所以直接赋值
  
  此时数组顺序变成了：13，49，37，86，82，66，87，跟我们前面测试结果一致

结论

• 数组的顺序是无序排列
• 从根节点到叶子节点的分支，内部是有序的

3、出队分析

poll 源码：

    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }

poll 流程图：

如图所示：

• 如果当前数组的数据超过1个，会先执行 siftDown 方法
• 方法最后一定是返回 result （数组第1个元素）。因此我们可以大胆猜测，siftDown 执行完毕后，数组的第1个元素一定是最小的

出队拆解：

初始状态

第1次出队

前面我们说过，执行 siftDown 之后，队列顶部一定是最小的元素。第1次出队的数据是13，之后最小的元素一定是13的两个子节点之一。因此，siftDown 的第1步就是找到左右两个子节点，把比较小的元素移动到根节点。

如下代码所示：

	//k：此处值是 0
	//x：当前数组最后一个元素
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        //size：数组最后一个元素的下标值
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
        	//找到左侧子节点
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            //找到右侧子节点
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                //如果右侧子节点更小，就赋值给c。因此，c记录的是最小的数据
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            //把最小的数据（变量c）往上移
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

代码中while第一次循环结束后，数组结构如下。37 < 49，所以37被移到根节点。

但是，下标2仍然记录着37，所以下一步就是把 k 设置成下标2，然后重复执行前面的步骤：获取37的左右节点，把最小的往上移。如下图所示：

第三次while循环时，k 变成 5，已经没有下级节点了，所以循环结束。

最后执行 queue[k] = key ，也就是把最后一个元素设置成左节点

第2次出队、第3次出队等等，原理都一样的，这里就不逐一说明了

4、总结

• PriorityQueue执行入队和出队时，都会进行排序比较。因此入队的对象必须实现 Comparable 接口，或者在实例化PriorityQueue对象的时候定义 Comparator 方法（构造函数传参）
• PriorityQueue 是非线程安全的，多线程环境必须使用 PriorityBlockingQueue
• PriorityQueue 入队时间复杂度是O(log)，因为要维护树的层级关系
• PriorityQueue 出队时间复杂度是O(log)，原因同上