前言
Queue（队列）是拥有先进先出（FIFO）特性的数据结构，PriorityQueue（优先级队列）是它的子类之一，不同于先进先出，它可以通过比较器控制元素的输出顺序（优先级）。本文就来分析一下PriorityQueuede的源码，看看它是如何实现的。
类继承关系
先来看Queue接口：
public interface Queue<E> extends Collection<E>
Queue接口继承了Collection接口，表示集合。它提供了三种方法，即：增加、删除、获取，每种都有两个实现。
// 增加元素
boolean add(E e);
boolean offer(E e);
// 删除元素
E remove();
E poll();
// 获取元素
E element();
E peek();
两种实现的区别是，add、remove和element都比对应的offer、poll和peek多抛出一个异常。对于add方法，如果因为容量不足以增加新元素，会抛出IllegalStateException异常，而offer则会返回false。对于remove方法，如果队列是空的，则会抛出NoSuchElementException异常，而poll方法会返回null。对于element方法，如果队列是空的，则会抛出NoSuchElementException异常，而peek方法会返回null。
再看PriorityQueue类：
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable
嗯，不是直接实现Queue，而是继承了AbstractQueue类。又是熟悉的感觉，AbstractQueue应该也是模板抽象类（和AbstractMap和AbstractList类似）。
来看AbstractQueue：
public abstract class AbstractQueue<E>
extends AbstractCollection<E>
implements Queue<E>
果然，继承了AbstractCollection类和实现了Queue接口。既然是模板类那肯定有模板方法。AbstractQueue源码中只实现了add、remove和elemet方法。
public boolean add(E e) {
if (offer(e)) // 调用offer
...
}
public E remove() {
E x = poll(); // 调用poll
...
}
public E element() {
E x = peek(); // 调用peek
...
}
可以看到，它们分别调用了offer、poll和peek。也就是说，如果要通过AbstractQueue实现队列，则必须实现offer、poll和peek方法。
下面就正紧的分析PriorityQueue的源码了。
PriorityQueue源码分析
纵观源码，发现PriorityQueue是通过“极大优先级堆”实现的，即堆顶元素是优先级最大的元素。算是集成了大根堆和小根堆的功能。
重要属性
根据堆的特性，存储结构肯定是数组了；既然支持不同优先级，肯定有比较器，也就是说支持自定义排序和顺序排序。
// 默认容量11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 堆的存储结构，存储元素
transient Object[] queue; // 不可序列化
// 当前存储的元素数量
int size;
// 比较器，确定优先级高低
private final Comparator<? super E> comparator;
// 避免OOM，数组可以分配的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造函数
PriorityQueue的构造函数有很多，主要参数是容量和比较器：
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null); // 默认自然序
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null); // 自定义初始容量
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator); // 自定义比较器
}
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
... // 对应赋值
}
public PriorityQueue(Collection<? extends E> c) {
// 将c转成堆
if (c instanceof SortedSet<?>) {
... // SortedSet自带比较器
}
else if (c instanceof PriorityQueue<?>) {
... // PriorityQueue自带比较器
}
else {
...
}
}
public PriorityQueue(PriorityQueue<? extends E> c) {
... // 从PriorityQueue获取比较器，将c转成堆
}
public PriorityQueue(SortedSet<? extends E> c) {
...// 从SortedSet获取比较器，将c转成堆
}
重用方法
PriorityQueue是支持扩容的，先来看扩容方法：
// minCapacity表示需要的最小容量
private void grow(int minCapacity) {
int oldCapacity = queue.length; // 获取当前容量
// Double size if small; else grow by 50%
// 如果旧容量小于64，则增加旧容量+2的大小
// 如果旧容量大于等于64，则增加旧容量的一半大小
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0) // 这里处理大容量
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity); // 复制已存储的数据
}
每次扩展的容量大小还是挺大的，要么变为原来的双倍，要么增长一半大小。
在看增加元素、删除元素和获取元素的方法之前，先了解以下几点：
- 完全二叉树的最后一个非叶子结点的下标是 (n-2) / 2；
- 完全二叉树中如果一个非叶子结点的下标是i，则它的父结点下标是（i-1）/2，它的左孩子下标是 2 * i + 1，右孩子下标是 2 * i + 2；
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; // 当前大小加1
return true;
}
siftUp方法最终会调用siftUpUsingComparator或者siftUpComparable方法，两个实现类似，这里直接看siftUpUsingComparator方法。
// 上移就是不断和父结点比较
private static <T> void siftUpUsingComparator(
int k, T x, Object[] es, Comparator<? super T> cmp) {
while (k > 0) {
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;
}
每次增加元素，都要保证堆序。
poll方法
public E poll() {
final Object[] es;
final E result;
// 返回堆顶元素
if ((result = (E) ((es = queue)[0])) != null) {
modCount++;
final int n;
final E x = (E) es[(n = --size)]; // 把尾部元素换到第一个
es[n] = null;
if (n > 0) {
final Comparator<? super E> cmp;
if ((cmp = comparator) == null) // 自然序时，下移调整
siftDownComparable(0, x, es, n);
else // 自定义序下移调整
siftDownUsingComparator(0, x, es, n, cmp);
}
}
return result;
}
poll方法会返回队首元素（堆顶），并将元素从堆中删除。删除过程，是将第一个元素与最后一个元素进行替换，然后再进行下移调整操作。这里直接看siftDownUsingComparator方法：
private static <T> void siftDownUsingComparator(
int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
// assert n > 0;
int half = n >>> 1; // 最后一个非叶子结点下标（因为size已经减1了）
while (k < half) {
int child = (k << 1) + 1; // 左孩子
Object c = es[child];
int right = child + 1; // 右孩子
if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
c = es[child = right]; // 从左右孩子中挑选优先级高的
if (cmp.compare(x, (T) c) <= 0)
break;
es[k] = c; // 将目标元素下移
k = child;
}
es[k] = x;
}
每次弹出队首元素，都要进行堆调整。
remove方法
poll方法可以看出是remove方法的特例，即固定删除第一个元素。
public boolean remove(Object o) {
int i = indexOf(o); // 找到待删除元素位置
if (i == -1)
return false;
else {
removeAt(i); // 删除指定位置元素
return true;
}
}
调用了removeAt方法：
E removeAt(int i) {
// assert i >= 0 && i < size;
final Object[] es = queue;
modCount++;
int s = --size; // size已经减1
if (s == i) // removed last element
es[i] = null; // 已经删除到最后一个元素
else {
E moved = (E) es[s]; // 尾元素
es[s] = null;
siftDown(i, moved); // 指定元素换尾元素，然后调整
if (es[i] == moved) {
siftUp(i, moved); // 如果指定位置换成了尾元素（没有发生下移）则进行上移操作
if (es[i] != moved)
return moved;
}
}
return null; // 正常删除时返回null
}
总结
- PriorityQueue是基于最大优先级堆实现的，根据比较器的情况可以是大根堆或者小根堆；
- PriorityQueue不支持null；
- PriorityQueue不是线程安全的，多线程环境下可以使用
java.util.concurrent.PriorityBlockingQueue； - 使用
iterator()遍历时，不保证输出的序列是有序的，其实遍历的是存储数组。
关注微信公众号，最新技术干货实时推送
image
网友评论