优先队列 PriorityQueue 是 接口 Queue的实现，可以对其中元素进行排序，可以放基本的包装类型或自定义类型，对于包装类型默认为升序，对于自定义类型需手动实现 Comparator 接口。
实现：
PriorityQueue 采用 堆排序，头是按指定排序方式的最小元素，堆排序只能保证根室最大 / 最小，整个堆并不是有序的。若想按特定顺序遍历，可先调用toArray方法将其转为数组，然后使用Arrays.sort()排序遍历。
优先队列是允许至少下列两种操作的数据结构：insert（插入）、deleteMin（删除最小者），在Java 中体现为 offer 方法和 poll 方法，它们等价于入队、出队操作。
二叉堆（binary heap）
一般借助二叉堆实现优先队列，它有两个性质：结构性、堆序性，一般使用数组实现即可：
堆是一棵完全二叉树，对数组中任一位置i上的元素，其左子节点在位置 2i 上，右子节点在 (2i + 1) 上，它的父节点在 ⌊i / 2⌋ 上。
堆序性质（heap-order property）
让操作快速执行的性质是 堆序性质，最小元位于根上，任一节点元素都小于其后裔元素。
基本操作:
insert（插入）—— percolate up（上滤）
为将一个元素插入堆中，在下一个可用位置处创建一个空穴。若X放入不破坏堆序，则完成插入；否则，我们将空穴的父节点元素移入该空穴，原父节点成为新的空穴，重复此过程，直至满足堆序性质即可，这种策略称为 上滤。
deleteMin（删除最小元）—— percolate down（下滤）
删除13之后，试图再次正确地将末置位31放入堆中，除非堆内所有元素相等，否则必定因破坏堆序性质而无法放入。可将较小子元素14置入空穴，空穴下滑一层，重复该过程，直至寻找到合适的空穴，这种策略称为 下滤。
Java 中内置了优先队列的实现 PriorityQueue 类（线程不安全），我们可以通过对它的解析，进一步理解优先队列的实现。
PriorityQueue 类内置了很多属性，对其构成、使用十分重要：
① 默认容量大小
//队列内置数组默认长度
private static final int DEFAULT_INITIAL_CAPACITY = 11;
代表队列内置数组默认长度
② 默认 Comparator 接口
@SuppressWarnings("serial") // Conditionally serializable
private final Comparator<? super E> comparator;
我们在使用 自定义类型 实例作为优先队列的元素时，需完成以下操作之一：
Comparable 接口，并实现相应的方法Comparator 接口的 匿名内部类 （可使用lambda表达式替换）作为参数传入构造方法， 该引用 指向创建的内部类实例PriorityQueue<Car> pq = new PriorityQueue<>(new Comparator<Car>() {
@Override
public int compare(Car c1, Car c2) {
return c1.getId() - c2.getId();
}
});
若未完成指定操作，则会抛出ClassCastException异常，这是因为内部comparator默认为空，则认为类型本身已实现Comparable接口，并尝试进行类型转换：
③ 变化量
//注释原文
//The number of times this priority queue has been structurally modified
//注释翻译
//优先队列被更改的次数
transient int modCount; // non-private to simplify nested class access
当 结构 / 元素 被更改时，变化量会增加
④ 平衡二叉堆（数组）
/** 注释原文
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
/** 注释翻译
* 优先队列 基于 平衡二叉堆，queue[n]的两个孩子为queue[2*n+1]、queue[2*(n+1)]。
* 优先队列根据Comparator接口的实现排序，或根据元素的自然顺序
* 若 comparator 属性为空，对于堆中每个节点n 都有其每个后裔节点d（n <= d）。
* 若队列非空，最小的元素保存在queue[0]
*/
transient Object[] queue; // non-private to simplify nested class access
优先队列底层基于该数组实现（二叉堆载体）
PriorityQueue 类内置了很多实用方法：
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; //成功插入元素
}
grow - 数组扩容
/**
* 数组扩容
* Increases the capacity of the array.
*
* @param 最小期望容量
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
int oldCapacity = queue.length; //旧数组长度
// Double size if small; else grow by 50%
//ArraysSupport类的newLength方法可计算新数组的长度
//传入三个参数：旧长度、最小增长、期望增长
//newLength(int oldLength, int minGrowth, int prefGrowth)
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth 最小增长长度*/
oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
/* preferred growth 期望增长：
旧长度 < 64：增长2
旧长度 >= 64：增长原先50%*/);
queue = Arrays.copyOf(queue, newCapacity);
}
siftUp - 插入元素
private void siftUp(int k, E x) {
if (comparator != null) //未传入 comparator 实例
siftUpUsingComparator(k, x, queue, comparator);
else //传入 comparator 实例
siftUpComparable(k, x, queue);
}
若我们传入了一个构造器，我们就调用siftUpUsingComparator(k, x)，否则调用 siftUpComparable(k, x)方法，这里以siftUpComparable为例：
siftUpComparable - 插入元素
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x; //将目标元素强转为 Comparable
while (k > 0) { //第k个元素 > 0
int parent = (k - 1) >>> 1; //记录第k个位置的父节点索引
Object e = es[parent]; //记录父节点元素
if (key.compareTo((T) e) >= 0) //调用compareTo方法比较两元素，若该元素大于父节点元素，证明无需再“上滤(percolate up)”
break; //退出循环
//父元素与k 交换位置
es[k] = e;
k = parent;
}
es[k] = key; //放入元素
}
public E poll() {
//记录队列数组
final Object[] es;
//需要返回的元素：结果
final E result;
if ((result = (E) ((es = queue)[0])) != null) { //queue[0]不为空
modCount++; //元素出队列，元素更改，变化值 +1
final int n; //
final E x = (E) es[(n = --size)]; //记录末置位值
es[n] = null; //末置位置空
if (n > 0) { //末置位索引 ＞ 0
final Comparator<? super E> cmp; //comparator 引用
if ((cmp = comparator) == null) //comparator 为空
siftDownComparable(0, x, es, n); //未使用 Comparator 方法
else
siftDownUsingComparator(0, x, es, n, cmp); //使用 Comparator 方法
}
}
return result; //返回结果
}
同样，若我们传入了一个构造器，我们就调用siftDownUsingComparator(k, x)，否则调用 siftDownComparable(k, x)方法，这里以siftDownComparable为例：
siftDownComparable - 删除元素
private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
// assert n > 0;
Comparable<? super T> key = (Comparable<? super T>)x; //将目标元素强转为 Comparable
int half = n >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = es[child]; //保存子节点元素
int right = child + 1; //右子节点
if (right < n &&
((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
c = es[child = right];
if (key.compareTo((T) c) <= 0) //调用compareTo方法比较两元素，若该元素小于子节点元素，证明无需再“下滤(percolate down)”
break; //退出循环
//子节点与k 交换位置
es[k] = c;
k = child;
}
es[k] = key; //放入元素
}
public E peek() {
return (E) queue[0];
}
插入、删除 复杂度O(n)