PriorityQueue - tenji/ks GitHub Wiki
PriorityQueue 其实是一个优先队列，和先进先出（FIFO）的队列的区别在于，优先队列每次出队的元素都是优先级最高的元素。那么怎么确定哪一个元素的优先级最高呢，JDK 中使用堆这么一种数据结构，通过堆使得每次出队的元素总是队列里面最小的，而元素的大小比较方法可以由用户 Comparator 指定，这里就相当于指定优先级。
堆的特点：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全树。
常见的堆有二叉堆、斐波那契堆等。而 PriorityQueue 使用的便是二叉堆，这里我们主要来分析和学习二叉堆。
二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
我们以最小堆为例，用图解来描述下什么是二叉堆。
上图就是一颗完全二叉树（二叉堆），我们可以看出什么特点吗，那就是在第 n 层深度被填满之前，不会开始填第 n+1 层深度，而且元素插入是从左往右填满。
基于这个特点，二叉堆用数组来表示而不是用链表，我们来看一下：
通过"用数组表示二叉堆"这张图，我们可以看出什么规律吗？那就是，基于数组实现的二叉堆，对于数组中任意位置的 n 上元素，其左孩子在 [2n+1] 位置上，右孩子 [2(n+1)] 位置，它的父亲则在 [(n-1)/2] 上，而根的位置则是 [0]。
好了，在了解了二叉堆的基本概念后，我们来看下 JDK 中 PriorityQueue 是怎么实现的。
先来看下 PriorityQueue 的定义：
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {我们看到 PriorityQueue 继承了 AbstractQueue 抽象类，并实现了 Serializable 接口，AbstractQueue 抽象类实现了 Queue 接口，对其中方法进行了一些通用的封装，具体就不多看了。
下面再看下 PriorityQueue 的底层存储相关定义：
// 默认初始化大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 用数组实现的二叉堆，下面的英文注释确认了我们前面的说法。
/**
* 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.
*/
private transient Object[] queue ;
// 队列的元素数量
private int size = 0;
// 比较器
private final Comparator<? super E> comparator;
// 修改版本
private transient int modCount = 0;我们看到 JDK 中的 PriorityQueue 的也是基于数组来实现一个二叉堆，并且注释中解释了我们前面的说法。而 Comparator 这个比较器我们已经很熟悉了，我们说 PriorityQueue 是一个有限队列，他可以由用户指定优先级，就是靠这个比较器。
/**
* 默认构造方法，使用默认的初始大小来构造一个优先队列，比较器 comparator 为空，这里要求入队的元素必须实现 Comparator 接口
*/
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* 使用指定的初始大小来构造一个优先队列，比较器 comparator 为空，这里要求入队的元素必须实现 Comparator 接口
*/
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) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
// 初始大小不允许小于1
if (initialCapacity < 1)
throw new IllegalArgumentException();
// 使用指定初始大小创建数组
this.queue = new Object[initialCapacity];
// 初始化比较器
this.comparator = comparator;
}
/**
* 构造一个指定 Collection 集合参数的优先队列
*/
public PriorityQueue(Collection<? extends E> c) {
// 从集合c中初始化数据到队列
initFromCollection(c);
// 如果集合c是包含比较器Comparator的(SortedSet/PriorityQueue)，则使用集合c的比较器来初始化队列的Comparator
if (c instanceof SortedSet)
comparator = (Comparator<? super E>)
((SortedSet<? extends E>)c).comparator();
else if (c instanceof PriorityQueue)
comparator = (Comparator<? super E>)
((PriorityQueue<? extends E>)c).comparator();
// 如果集合c没有包含比较器，则默认比较器Comparator为空
else {
comparator = null;
// 调用heapify方法重新将数据调整为一个二叉堆
heapify();
}
}
/**
* 构造一个指定 PriorityQueue 参数的优先队列
*/
public PriorityQueue(PriorityQueue<? extends E> c) {
comparator = (Comparator<? super E>)c.comparator();
initFromCollection(c);
}
/**
* 构造一个指定 SortedSet 参数的优先队列
*/
public PriorityQueue(SortedSet<? extends E> c) {
comparator = (Comparator<? super E>)c.comparator();
initFromCollection(c);
}
/**
* 从集合中初始化数据到队列
*/
private void initFromCollection(Collection<? extends E> c) {
// 将集合Collection转换为数组a
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
// 如果转换后的数组a类型不是Object数组，则转换为Object数组
if (a.getClass() != Object[].class)
a = Arrays. copyOf(a, a.length, Object[]. class);
// 将数组a赋值给队列的底层数组queue
queue = a;
// 将队列的元素个数设置为数组a的长度
size = a.length ;
}构造方法还是比较容易理解的，第四个构造方法中，如果填入的集合 c 没有包含比较器 Comparator，则在调用 initFromCollection 初始化数据后，在调用 heapify 方法对数组进行调整，使得它符合二叉堆的规范或者特点，具体 heapify 是怎么构造二叉堆的，我们后面再看。
那么怎么样调整才能使一些杂乱无章的数据变成一个符合二叉堆的规范的数据呢？
红黑树为了维护其红黑平衡，主要有三个动作：左旋、右旋、着色。那么二叉堆为了维护他的特点又需要进行什么样的操作呢？
我们再来看下二叉堆（最小堆为例）的特点：
- 父结点的键值总是小于或等于任何一个子节点的键值；
- 基于数组实现的二叉堆，对于数组中任意位置的 n 上元素，其左孩子在
2n+1位置上，右孩子2(n+1)位置，它的父亲则在(n-1)/2上，而根的位置则是0
为了维护这个特点，二叉堆在添加元素的时候，需要一个“上移”的动作，什么是“上移”呢，我们继续用图来说明。
结合上面的图解，我们来说明一下二叉堆的添加元素过程：
- 将元素 2 添加在最后一个位置（队尾）；
- 由于 2 比其父亲 6 要小，所以将元素 2 上移，交换 2 和 6 的位置；
- 然后由于 2 比 5 小，继续将 2 上移，交换 2 和 5 的位置，此时 2 大于其父亲（根节点）1，结束。
注：这里的节点颜色是为了凸显，应便于理解，跟红黑树的中的颜色无关，不要弄混。
看完了这 4 张图，是不是觉得二叉堆的添加还是挺容易的，那么下面我们具体看下 PriorityQueue 的代码是怎么实现入队操作的吧。
/**
* 添加一个元素
*/
public boolean add(E e) {
return offer(e);
}
/**
* 入队
*/
public boolean offer(E e) {
// 如果元素 e 为空，则抛出空指针异常
if (e == null)
throw new NullPointerException();
// 修改版本 +1
modCount++;
// 记录当前队列中元素的个数
int i = size ;
// 如果当前元素个数大于等于队列底层数组的长度，则进行扩容
if (i >= queue.length)
grow(i + 1);
// 元素个数+1
size = i + 1;
// 如果队列中没有元素，则将元素 e 直接添加至根（数组下标 0 的位置）
if (i == 0)
queue[0] = e;
// 否则调用 siftUp 方法，将元素添加到尾部，进行上移判断
else
siftUp(i, e);
return true;
}这里的 add 方法依然没有按照 Queue 的规范，在队列满的时候抛出异常，因为 PriorityQueue 和前面讲的 ArrayDeque 一样，会进行扩容，所以只有当队列容量超出 int 范围才会抛出异常。
/**
* 数组扩容
*/
private void grow(int minCapacity) {
// 如果最小需要的容量大小 minCapacity 小于 0，则说明此时已经超出 int 的范围，则抛出 OutOfMemoryError 异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 记录当前队列的长度
int oldCapacity = queue .length;
// Double size if small; else grow by 50%
// 如果当前队列长度小于 64 则扩容后容量翻倍，否则扩容 50%
int newCapacity = ((oldCapacity < 64)?
((oldCapacity + 1) * 2):
((oldCapacity / 2) * 3));
// 如果扩容后 newCapacity 超出 int 的范围，则将 newCapacity 赋值为 Integer.Max_VALUE
if (newCapacity < 0) // overflow
newCapacity = Integer. MAX_VALUE;
// 如果扩容后，newCapacity 小于最小需要的容量大小 minCapacity，则按照 minCapacity 长度进行扩容
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// 数组 copy，进行扩容
queue = Arrays.copyOf( queue, newCapacity);
}好了，看完上面这个小插曲，我们来看下二叉堆的一个重要操作“上移”是怎么实现的吧。
/**
* 上移，x 表示新插入元素，k 表示新插入元素在数组的位置
*/
private void siftUp(int k, E x) {
// 如果比较器 comparator 不为空，则调用 siftUpUsingComparator 方法进行上移操作
if (comparator != null)
siftUpUsingComparator(k, x);
// 如果比较器 comparator 为空，则调用 siftUpComparable 方法进行上移操作
else
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
// 比较器 comparator 为空，需要插入的元素实现 Comparable 接口，用于比较大小
Comparable<? super E> key = (Comparable<? super E>) x;
// k > 0 表示判断 k 不是根的情况下，也就是元素 x 有父节点
while (k > 0) {
// 计算元素 x 的父节点位置 (n - 1) / 2
int parent = (k - 1) >>> 1;
// 取出 x 的父亲 e
Object e = queue[parent];
// 如果新增的元素 k 比其父亲 e 大，则不需要"上移"，跳出循环结束
if (key.compareTo((E) e) >= 0)
break;
// x 比父亲小，则需要进行"上移"
// 交换元素 x 和父亲 e 的位置
queue[k] = e;
// 将新插入元素的位置 k 指向父亲的位置，进行下一层循环
k = parent;
}
// 找到新增元素 x 的合适位置 k 之后进行赋值
queue[k] = key;
}
// 这个方法和上面的操作一样，不多说了
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator .compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}结合上面的图解，二叉堆“上移”操作的代码还是很容易理解的，主要就是不断的将新增元素和其父亲进行大小比较，比父亲小则上移，最终找到一个合适的位置。
对于二叉堆的出队操作，出队永远是要删除根元素，也就是最小的元素，要删除根元素，就要找一个替代者移动到根位置，相对于被删除的元素来说就是“下移”。
结合上面的图解，我们来说明一下二叉堆的出队过程：
- 将找出队尾的元素 8，并将它在队尾位置上删除（图2）;
- 此时队尾元素 8 比根元素 1 的最小孩子 3 要大，所以将元素 1 下移，交换 1 和 3 的位置（图3）；
- 然后此时队尾元素 8 比元素 1 的最小孩子 4 要大，继续将 1 下移，交换 1 和 4 的位置（图4）；
- 然后此时根元素 8 比元素 1 的最小孩子 9 要小，不需要下移，直接将根元素 8 赋值给此时元素 1 的位置，1 被覆盖则相当于删除（图5），结束。
看完了这6张图，下面我们具体看下 PriorityQueue 的代码是怎么实现出队操作的吧。
/**
* 删除并返回队头的元素，如果队列为空则抛出 NoSuchElementException 异常（该方法在 AbstractQueue 中）
*/
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
/**
* 删除并返回队头的元素，如果队列为空则返回 null
*/
public E poll() {
// 队列为空，返回 null
if (size == 0)
return null;
// 队列元素个数 -1
int s = --size ;
// 修改版本 +1
modCount++;
// 队头的元素
E result = (E) queue[0];
// 队尾的元素
E x = (E) queue[s];
// 先将队尾赋值为 null
queue[s] = null;
// 如果队列中不止队尾一个元素，则调用 siftDown 方法进行"下移"操作
if (s != 0)
siftDown(0, x);
return result;
}
/**
* 上移，x 表示队尾的元素，k 表示被删除元素在数组的位置
*/
private void siftDown(int k, E x) {
// 如果比较器 comparator 不为空，则调用 siftDownUsingComparator 方法进行下移操作
if (comparator != null)
siftDownUsingComparator(k, x);
// 比较器 omparator 为空，则调用 siftDownComparable 方法进行下移操作
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
// 比较器 comparator 为空，需要插入的元素实现 Comparable 接口，用于比较大小
Comparable<? super E> key = (Comparable<? super E>)x;
// 通过 size / 2 找到一个没有叶子节点的元素
int half = size >>> 1; // loop while a non-leaf
// 比较位置 k 和 half，如果 k 小于 half，则 k 位置的元素就不是叶子节点
while (k < half) {
// 找到根元素的左孩子的位置 2n + 1
int child = (k << 1) + 1; // assume left child is least
// 左孩子的元素
Object c = queue[child];
// 找到根元素的右孩子的位置 2 * (n + 1)
int right = child + 1;
// 如果左孩子大于右孩子，则将 c 复制为右孩子的值，这里也就是找出左右孩子哪个最小
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue [right]) > 0)
c = queue[child = right];
// 如果队尾元素比根元素孩子都要小，则不需"下移"，结束
if (key.compareTo((E) c) <= 0)
break;
// 队尾元素比根元素孩子都大，则需要"下移"
// 交换跟元素和孩子 c 的位置
queue[k] = c;
// 将根元素位置 k 指向最小孩子的位置，进入下层循环
k = child;
}
// 找到队尾元素 x 的合适位置 k 之后进行赋值
queue[k] = key;
}
// 这个方法和上面的操作一样，不多说了
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue [right]) > 0)
c = queue[child = right];
if (comparator .compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}JDK 中，不是直接将根元素删除，然后再将下面的元素做上移，重新补充根元素；而是找出队尾的元素，并在队尾的位置上删除，然后通过根元素的下移，给队尾元素找到一个合适的位置，最终覆盖掉跟元素，从而达到删除根元素的目的。这样做在一些情况下，会比直接删除在上移根元素，或者直接下移根元素再调整队尾元素的位置少操作一些步奏（比如上面图解中的例子，不信你可以试一下^_^）。
明白了二叉堆的入队和出队操作后，其他的方法就都比较简单了，下面我们再来看一个二叉堆中比较重要的过程，二叉堆的构造。
我们在上面提到过的，堆的构造是通过一个 heapify 方法，下面我们来看下 heapify 方法的实现。
/**
* Establishes the heap invariant (described above) in the entire tree,
* assuming nothing about the order of the elements prior to the call.
*/
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}这个方法很简单，就这几行代码，但是理解起来却不是那么容器的，我们来分析下。
假设有一个无序的数组，要求我们将这个数组建成一个二叉堆，你会怎么做呢？最简单的办法当然是将数组的数据一个个取出来，调用入队方法。但是这样做，每次入队都有可能会伴随着元素的移动，这么做是十分低效的。那么有没有更加高效的方法呢，我们来看下。
为了方便，我们将上面我们图解中的数组去掉几个元素，只留下 7、6、5、12、10、3、1、11、15、4（顺序已经随机打乱）。ok、那么接下来，我们就按照当前的顺序建立一个二叉堆，暂时不用管它是否符合标准。
int a = [7, 6, 5, 12, 10, 3, 1, 11, 15, 4 ];
我们观察下用数组 a 建成的二叉堆，很明显，对于叶子节点 4、15、11、1、3 来说，它们已经是一个合法的堆。所以只要最后一个节点的父节点，也就是最后一个非叶子节点 a[4]=10 开始调整，然后依次调整 a[3] = 12，a[2] = 5，a[1] = 6，a[0] = 7，分别对这几个节点做一次"下移"操作就可以完成了堆的构造。ok，我们还是用图解来分析下这个过程。
我们参照图解分别来解释下这几个步奏：
- 对于节点 a[4] = 10 的调整（图1），只需要交换元素 10 和其子节点 4 的位置（图2）。
- 对于节点 a[3] = 12 的调整，只需要交换元素 12 和其最小子节点 11 的位置（图3）。
- 对于节点 a[2] = 5 的调整，只需要交换元素 5 和其最小子节点 1 的位置（图4）。
- 对于节点 a[1] = 6 的调整，只需要交换元素 6 和其最小子节点 4 的位置（图5）。
- 对于节点 a[0] = 7 的调整，只需要交换元素 7 和其最小子节点 1 的位置，然后交换 7 和其最小节点 3 的位置（图6）。
至此，调整完毕，建堆完成。
再来回顾一下，PriorityQueue 的建堆代码，看看是否可以看得懂了。
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}int i = (size >>> 1) - 1，这行代码是为了找寻最后一个非叶子节点，然后倒序进行"下移" siftDown 操作，是不是很显然了。
到这里 PriorityQueue 的基本操作就分析完了，明白了其底层二叉堆的概念及其入队、出队、建堆等操作，其他的一些方法代码就很简单了，这里就不一一分析了。
PriorityQueue 完！