概述
阅读 Java 版本为 1.8.0.25。
PriorityQueue 即优先队列，也是一个非常重要的队列实现形式，通过堆实现。
优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素)。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。
然后说下，在排序算法中，有一个高效并且消耗内存少的排序方法 -- 堆排序。堆排序算法应该是网上到处都是，可以自行百度。
还是和以前一样，将 PriorityQueue 源码以及相关类拷贝至自定义包内，进行注释添加，代码请移步：
https://gitee.com/qianwei4712/JDK1.8.0.25-read/blob/master/src/main/java/java/util/PriorityQueue.java
知识点总结如下：
堆的简单介绍
堆有2个概念：第一个是内存里面的堆，也就是静态链表；第二个堆是数据结构里的 二叉堆BinaryHeap，JDK 里表现为 PriorityQueue 优先队列 。
Java 中 PriorityQueue 通过堆实现，具体说是通过完全二叉树(complete binary tree)实现的小顶堆 ，然后是最小堆的定义：
- 是一个完全二叉树
- 任意节点的值小于等于左右两个孩子的值（如果有）
- 任意非叶子节点的左右子树也都是堆
堆的下标关系：
- 根节点下标为0
- 若节点 P 的下标为 i，则左孩子为 2i+1，右孩子为 2i+2
- 若节点 P 的下标为 i，则父节点的下标为 (i-1)/2
堆是一个典型的，用物理上线性表示逻辑上非线性的数据结构 ，例如下面这个例子的下标排列顺序
PriorityQueue构造方法
PriorityQueue 底层字段如下，经有4个字段，底层基于数组实现。
modCount 字段在 ArrayList 中做了详细解释，原本是 AbstractList 的 protected 字段。不过 PriorityQueue 没继承，就定义了一个，用于线程不安全情况下的快速失败判断机制。
//底层使用数组实现
transient Object[] queue; // 非私有以简化嵌套类访问
//优先队列元素个数
private int size = 0;
//优先队列比较器，如果为null,优先队列使用元素的自然顺序。
private final Comparator<? super E> comparator;
//修改次数，fast-fail机制，因为没有继承 AbstractList，所以需要自行定义。
transient int modCount = 0;
PriorityQueue 静态常量如下：
//默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//数组最大容量，实际值为2^31-1-8，超出会爆OutOfMemoryError。
//数组除了存放数据外，还有一个length属性，减8为了存放数组长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
PriorityQueue 的构造方法是我目前知道的最多的，有7个构造方法。。
因为 PriorityQueue 我基本没用过。。只能凭个人感觉哪些构造方法比较重要贴下了。
//无参构造器，默认数组长度 11；无比较器，元素按照顺序排序
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
//指定长度，没有比较器的构造函数，元素按照顺序排序
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
//创建一个带有比较器的优先队列，其元素根据比较器进行排序。默认长度 11
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
//指定初始化长度和比较器的构造器，其元素根据比较器进行排序
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
//如果参数长度是 1，抛出异常。。
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
无参构造器，默认数组长度 11
上面这套构造方法是基础的根据参数来构造对象。然后是根据其他 Collection 类创建
//根据 Collection集合 创建优先队列
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
//如果原始 collection 类型是 SortedSet的实现类
//直接赋值 SortedSet 的比较器，再初始化数组
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
//直接初始化有序集合
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
//如果原始 collection 类型是 PriorityQueue，同一类型的初始化就比较简单了
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
//初始化同类型队列
initFromPriorityQueue(pq);
}
else {
//正常的 Collection，没有比较器，默认为一个顺序容器
this.comparator = null;
//没有比较器，不需要进行排序，默认顺序容器，并将数组转化为堆
initFromCollection(c);
}
}
SortedSet 是一个自动排序不重复的 Collection 集合，接口设计要求实现一个 comparator 比较器，和优先队列 PriorityQueue 一样，所以构造方法中特对 SortedSet 地进行了判断。
构造方法中的几个调用细节在下面 具体操作时候再讲，包括堆排序，其实感觉根据有序集合构造的情况应该不多。。。
PriorityQueue的常用方法
PriorityQueue 是一个队列，队列的方法以前介绍过，不过 PriorityQueue 不是一个正常的先进先出队列。
add(E e) 和 offer(E e)
先看看添加元素方法的代码：
//将指定的元素插入此优先队列
public boolean add(E e) {
return offer(e);
}
//将指定的元素插入此优先队列
public boolean offer(E e) {
//不允许插入 null
if (e == null)
throw new NullPointerException();
//队列操作数+1
modCount++;
//当前队列元素
int i = size;
//如果当前队列元素个数大于等于数组长度
//数组已经填充满了，进行扩容
if (i >= queue.length)
grow(i + 1);
//队列元素个数+1
size = i + 1;
if (i == 0)
//如果原队列是空队列
queue[0] = e;
else
//根据元素进行筛选
siftUp(i, e);
return true;
}
首先这里可以看出
PriorityQueue 不允许添加 null。
然后就是，空队列第一个元素位置是 queue[0] 位置。然后是元素筛选的逻辑：
/**
* 将项目x插入位置k，通过将x提升到树上直到其大于或等于其父级或成为根，从而保持堆不变。
* 简化并加快强制和比较。将自然比较和比较器比较分为不同的方法，这些方法在其他方面相同。
* @param k 需要插入的位置
* @param x 需要加入的元素
*/
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
然后再看自然比较，就是使用存储对象自带的比较器
//没有比较器，使用自然比较
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
//将需要比较的元素转为 Comparable
Comparable<? super E> key = (Comparable<? super E>) x;
//如果插入下标大于0
//如果是根结点那就不需要重新筛选了。只有一个元素
while (k > 0) {
//根据堆的特性获得父节点的下标，(i-1)/2
int parent = (k - 1) >>> 1;
//获得父节点元素
Object e = queue[parent];
//比较器比较，如果符合父节点小于等于插入元素则跳出
if (key.compareTo((E) e) >= 0)
break;
//否则将父节点放置到原插入位置，并继续循环
queue[k] = e;
k = parent;
}
//循环结束，确定位置
queue[k] = key;
}
然后这里看下第一句强转
Comparable<? super E> key = (Comparable<? super E>) x;
不是所有对象都可以强转的。。。。
我们在写 demo 的时候习惯性得使用 Integer，String 这些类，这些类都已经实现了 Comparable 接口；
但是如果要比较自定义类，那该类必须实现 Comparable 接口。
siftUpUsingComparator 使用优先队列的比较器也是相同原理，就不写了。
。。。。哦，然后再把刚刚插入元素的图解放一哈
poll()
弹出队列头元素，优先队列虽然是单向的，但是已经不是简单的先进先出了。。
在 add 方法中已经介绍，添加时会重新排序，所以弹出时也是按比较排序后结果输出。
//弹出队列头元素
@SuppressWarnings("unchecked")
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];
//将队尾置空，因为队头空了，要往前移动重新筛选
queue[s] = null;
//如果弹出后队列长度不是0，那需要重新排序
if (s != 0)
//将队尾元素放到队头，然后一层层往下移动
siftDown(0, x);
//排序后返回队头元素
return result;
}
然后这里主要是重新排序方法
/**
* 在位置 k 插入项 x，通过反复将 x 降级到树上小于或等于其子级或为叶子，从而保持堆不变。
* 简化并加快强制和比较。将自然比较和比较器比较分为不同的方法，这些方法在其他方面相同。
* @param k 需要填补的位置
* @param x 需要插入的元素
*/
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
//使用自然比较筛选
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
//将需要插入的元素转为 Comparable
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;
//获得左孩子
Object c = queue[child];
//获得右孩子的下标
int right = child + 1;
//条件1：右孩子不是空的
//条件2：左孩子比右孩子大
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;
}
基本逻辑和添加方法是一样的，只是添加方法是将元素从最底层往上移动，弹出方法是将指定元素从最上层往下移动。
grow() 扩容
然后再看下 add() 方法中出现的扩容方法，数组底层，扩容问题肯定是绕不开的。。。这个涉及到增删的效率。
//如果当前队列元素个数大于等于数组长度
//数组已经填充满了，进行扩容
if (i >= queue.length)
grow(i + 1);
首先可以看到，在 add() 方法中扩容的判断，当数组填充满才会扩容，并且传入参数是长度+1；
//扩容数组
private void grow(int minCapacity) {
//拿到旧长度
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
//原长度x小于64，就扩容为 2x+2
//原长度x大于等于64，扩容为 1.5倍，扩容一半
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// 有溢出意识的代码
if (newCapacity - MAX_ARRAY_SIZE > 0)
//获得最大长度，参数 minCapacity = oldCapacity + 1
newCapacity = hugeCapacity(minCapacity);
//复制数组
queue = Arrays.copyOf(queue, newCapacity);
}
//最大容量方法；minCapacity = oldCapacity + 1
private static int hugeCapacity(int minCapacity) {
//超出integer变为负数，抛出异常
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
老生常谈的问题了，而且似乎也没啥实际用处：
- 原长度 x 小于64，就扩容为 2x+2
- 原长度 x 大于等于64，扩容为 1.5倍，扩容一半
- 最小扩容长度（minCapacity）= 原长度（oldCapacity）+ 1，这是扩容方法调用是传入的参数
- 若按倍率扩容长度超出最大长度，需要用最小扩容长度进行判断
使用建议
首先看看复杂度：
- 堆排序的平均时间复杂度为O(nlogn),最坏情况也是O(nlogn)，快排的平均时间复杂度也是O(nlogn)，但是最坏情况是O(n²)。
- 堆排序是O(1)，快排是O(logn)。快排是递归调用，所以空间要求更多一些。
使用场景举例：
- 大数据量的筛选：求一亿个数字里面最小的10个数字
- 业务系统，优先处理 VIP客户 再处理 普通客户，需要自定义比较器。
参考文章
https://www.pdai.tech/md/java/collection/java-collection-PriorityQueue.html