文章目录
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)，原因同上