前言
优先队列 PriorityQueue 的实现其实就是数据结构堆的实现。对数据结构堆比较熟悉的，看 PriorityQueue 的源码会十分容易，无外乎堆的生成，堆的重建和堆元素删除算法。PriorityQueue 相比于其它的队列，它能够将队列的元素进行排序保存，但是方法都没有加锁，所以它是非线程安全的
变量
先看看堆的定义：
1.堆总是一颗完全二叉树
2.堆中某个节点的值总是不大于或不小于其父节点的值
因此，堆的元素是可以保存在数组中，节点 i 的左子节点下标是 2i+1, 右子节点下标是 2i+2。PriorityQueue 的元素都保证在数组 queue 中。
/**
* 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.
*/
transient Object[] queue; // non-private to simplify nested class accesssize 表示数组中保存的元素数量。
/** * The number of elements in the priority queue. */
private int size = 0;PriorityQueue 可以自定义比较器 Comparator，用来对插入的元素排序。如果不定义比较器，那么插入的元素必须实现 Comparator 接口。这是优先队列实现元素排序功能的前提。
/** * The comparator, or null if priority queue uses elements' * natural ordering. */
private final Comparator<? super E> comparator;插入
插入元素 PriorityQueue 提供了两个方法，add(E e) 和 offer(E e)，add(E e) 方法其实就是直接调用 offer(E e)。
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;
}当插入的元素直接插入末尾的，可能不符合的堆的规则，这时候需要对堆元素进行调整，使其满足堆的定义。
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x); //设置了比较器
else
siftUpComparable(k, x); //没有设置比较器
}没有设置比较器，插入的元素E x 必须是接口 Comparable 的子类，否则会报错。如 int 类型元素是可以直接插入的，因为 Integer 实现了 Comparable 接口。
public final class Integer extends Number implements Comparable<Integer>不管有没有设置比较器，堆调整算法是一样的。这里看没有设置比较器的堆调整源码。
可以看到 PriorityQueue 实现的是小顶堆。
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;
}小顶堆调整实现原理：插入 k 位置的元素 x,若大于父节点，x 直接保存在 k 位置；若小于父节点，x 和父节点交换位置，接着再和新位置的父节点进行比较，以此类推，直到将 x 保存到满足大于父节点，小于子节点的位置。
插入元素的时候，k 的初始位置是堆新增叶子节点的位置，即 size。
删除
删除元素比较简单，直接从数组遍历寻找到该元素，然后删除，并对堆进行重构调整。
public boolean remove(Object o) {
int i = indexOf(o); //寻找元素位置
if (i == -1)
return false;
else {
removeAt(i); //删除该元素
return true;
}
}
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null; //删除的元素位于堆尾，则不用堆重构
else {
//堆重构
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);//向下调整
if (queue[i] == moved) {
siftUp(i, moved); //向上调整
if (queue[i] != moved)
return moved;
}
}
return null;
}当删除一个元素，堆的大小减小一，那么之前堆尾的元素肯定需要往前移。所以，将堆尾元素 moved 放置在删除的元素的位置，然后进行调整使其符合堆的股则。那么如何调整呢？首先将 moved 和其子节点进行调整。
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
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;
// 将 x 与左右子节点比较，若都比左右子节点小，则不对换，否则将最小的节点和x对换
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}从 k 位置放置 x 元素后往下调整的思路如下：
将 x 与左右子节点比较，若都比左右子节点小，则不对换，调整结束。否则将最小的节点和 x 对换，x 调整到新位置后，再和其左右子节点比较，以此类推，直到调整结束。
再返回到 removeAt(int i) 方法中。
向下调整结束之后，若 moved 还是位于 i 位置，说明 i 位置的左右节点都比 moved 大。这时要考虑 moved 的父节点比 moved 大的情况了，所以这种情况还得向上调整。
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;
}
向上调整比较简单，直接不断和父节点比较，如比父节点小，则和父节点交换位置。
读取
PriorityQueue 提供了 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;
}堆的头元素被取出，相当于删除堆的跟节点，堆的重建和删除方法中是一样的，这里就不用再叙述了。