【1】 基础概念
PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序，而是按照队列元素的大小进行重新排序，这点从它的类名也可以看出来 。
基于优先级堆的无限优先级队列。优先级队列的元素根据其 Comparable 可比自然排序或队列构造时提供的比较器Comparator排序，具体取决于使用的构造函数。
PriorityQueue优先级队列不允许 null 元素。
依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致ClassCastException）。
它还需要对队列元素进行排序，PriorityQueue的元素有两种排序方式：
自然排序:
采用自然顺序的PriorityQueue集合中的元素对象都必须实现了Comparable接口，而且应该是同一个类的多个实例，否则可能导致ClassCastException异常。
定制排序
创建PriorityQueue队列时，传入一个Comparator对象，该对象负责对队列中的所有元素进行排序。
该队列的头是相对于指定排序的最小的元素。如果多个元素被绑定为最小值，则头部就是这些元素之一——绑定被任意断开。队列检索操作 poll、 remove、 peek和 element访问队列头部的元素。优先级队列是无界的，但其内部容量控制数组(用于存储队列中元素)大小。它始终至少与队列大小一样大。随着元素添加到优先级队列，其容量会自动增长。自动增长策略(扩容策略)未指定。
这个类及其迭代器实现了 Collection 和 Iterator 接口的所有可选方法。方法iterator()中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用Arrays.sort(pq.toArray())。
请注意，此实现是不同步的(非线程安全)。如果任何线程修改队列，则多个线程不应同时访问PriorityQueue实例。如果有需要，请使用线程安全类PriorityBlockingQueue。
另外，优先级队列提供了不同的时间效能：
- 入队和出队比如offer、poll、remove和add—O(logn)
- remove(Object)、contains(Object)–线性时间
- peek、element、size—恒定时间
【2】核心属性和构造
① 核心属性
// 默认初始化容量 private static final int DEFAULT_INITIAL_CAPACITY = 11; //保存元素的数组 transient Object[] queue; //数组中元素的个数 private int size = 0 //外部比较器，用来进行排序 private final Comparator<? super E> comparator //结构修改计数器 transient int modCount = 0; //数组的最大值--可容纳最大元素个数 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
② 构造函数
默认构造函数
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); }
如下所示，这里会根据initialCapacity实例化一个Object数组。也就是说底层核心数据结构就是数组。
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 if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; }
此外还提供了一系列根据初始集合实例化队列的构造函数比如：
public PriorityQueue(Collection<? extends E> c); public PriorityQueue(PriorityQueue<? extends E> c); public PriorityQueue(SortedSet<? extends E> c);
③ 数据结构
Object[] queue 也就是说这里使用了数组来存储元素。那么数据结构形式是什么呢？是小顶堆。也就是优先级队列在插入和移除元素的时候会不断调整，在逻辑上形成一个小顶堆的形式。
什么是小顶堆？其实表现形式就是一颗完全二叉树，并且叶子结点的值不小于父结点。
二叉树一般有两种存储结构，一种顺序结构，一种链式结构。顺序结构存储就是使用数组存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间浪费。
二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树，一般只有堆用数组来存储。如下所示，左侧为完全二叉树，右侧为非完全二叉树(存在空间浪费)。
什么是顺序存储(层序遍历)？
如下图所示，二叉树上标注了数组下标位置，从上到下，从左到右。
下标关系
已知双亲 (parent) 的下标，则：
左孩子(left)下标 = 2 * parent + 1; 右孩子(right) 下标 = 2 * parent + 2;
已知孩子（不区分左右） (child) 下标，则 双亲(parent) 下标 = (child - 1) / 2。
【3】核心方法
本文这里优先级队列实现是基于jdk1.8，其本质是一个小顶堆。
① add&offer
如下所示，add方法直接调用了offer方法。
public boolean add(E e) { return offer(e); }
offer这里会判断是否需要扩容，如果不需要扩容则将元素放到第一个位置或者适当位置。
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; }
② siftUp
根据是否有外部比较器来触发siftUpUsingComparator或者siftUpComparable。在位置k插入项x，通过在树上提升x直到它大于或等于其父项或是根项，保持堆不变。
// k表示当前元素个数，x 表示将要放入的元素 private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }
siftUpUsingComparator
使用外部比较器为元素E x找到合适位置。
// k表示当前元素个数，x 表示将要放入的元素 private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; // 如果x小于父节点，那么将会交换x k的位置 if (comparator.compare(x, (E) e) >= 0) break; //将parent结点移动到K,再次对K进行判断 queue[k] = e; k = parent; } queue[k] = x; }
这里核心在于int parent = (k - 1) >>> 1;也就是每次都会从数组的中间位置查找，如果对比结果大于0则直接跳出循环，否则继续循环。这个过程实际上就是向小顶堆插入数据的过程，找到比当前插入元素小的元素，交换位置。
siftUpComparable
这个与siftUpUsingComparator的唯一区别是其使用对象自身的compareTo比较两个元素大小。
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; }
③ poll
获取并移除queue[0]位置的元素，也就是移除堆顶的元素，这会导致堆的重新调整。
public E poll() { if (size == 0) return null; int s = --size; modCount++; //获取第 0 个元素 E result = (E) queue[0]; //获取最后一个元素 E x = (E) queue[s]; //修改queue[s] 位置为null queue[s] = null; //如果有两个以上的元素 if (s != 0) siftDown(0, x); return result; }
④ siftDown
这里k为0，指的是索引位置，x为目标元素。这里会从索引位置0开始依次遍历左右叶子结点，使左右叶子结点有机会上升，并为目标元素E x找到合适位置。
通常在使用数组初始化堆或者移除元素的时候，会触发向下调整
private void siftDown(int k, E x) { if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); }
siftDownComparable与siftDownUsingComparator的根本区别在于前者使用对象自身的compareTo方法，后者使用外部比较器comparator。
private void siftDownComparable(int k, E x) { // 类型转换后的x Comparable<? super E> key = (Comparable<? super E>)x; // size是当前元素个数 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; //左叶子结点大于右叶子结点 if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) // 这里如果c>right，那么会更新child c 到right侧，也就是取小的一侧 // child=right // c=queue[right] c = queue[child = right]; //最后一个结点是否小于c--要么是c自身，要么是C的父节点 if (key.compareTo((E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = key; } @SuppressWarnings("unchecked") 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; }
假设有如下11个元素构成的小顶堆，表现形式如下二叉树。我们分析移除堆顶元素的过程。
第二次：k=1,child=3,c=22,queue[right]=queue[4]=18,也就是左叶子结点大于右叶子结点，那么会触发c = queue[child = right]，这时c就变成了18，child=4。经过比较判断后结果queue[k]=queue[1]=18,k=child=4;
第三次：k=4,child=9,c=23,queue[right]=queue[10]=19,这时候right已经等于size，是最后一个元素将直接break。queue[k] = x;，也就是queue[4]=19。
其实整体来看，其移除元素的过程则是首先移除了堆顶元素，并记录了最后一个元素。然后从堆顶元素开始寻找其最小的叶子节点依次上移完成堆的调整。
为什么while的条件是k<half？因为最后按照完全二叉树来说，最后一个父节点必然是(length>>>1)-1，所以k最多遍历到最后一个父节点，这时就意味着已完成了可能的遍历。
⑤ peek
peek只是获取堆顶元素也就是数组的第一个元素并不会导致结构发生变化。
public E peek() { return (size == 0) ? null : (E) queue[0]; }
⑥ 扩容grow
这里minCapacity=size+1，这里会确定新数组长度然后新建数组进行数据值拷贝。newCapacity 依据如下规则扩容：如果小于64，则2倍原始长度+2，否则，1.5倍原始长度
private void grow(int minCapacity) { //原始长度 int oldCapacity = queue.length; // Double size if small; else grow by 50% // 如果小于64，则2倍原始长度+2，否则，1.5倍原始长度 int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) // newCapacity =Integer.MAX_VALUE newCapacity = hugeCapacity(minCapacity); //新建数组，拷贝进来 queue = Arrays.copyOf(queue, newCapacity); }
⑦ 堆化
private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); }
仍旧以下图为例，默认初始化11个元素。那么按照上面代码其实也就是从i=4开始到i=0结束，对每个父节点进行与子节点的大小对比。每一个父节点都经过一遍siftDown过程。
⑧ 移除元素remove
remove(Object o)首先获取元素在队列中的索引，然后交给 removeAt(i)来处理。
public boolean remove(Object o) { int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } }
removeAt方法如下所示：
private E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; // 判断是否为最后一个元素 if (s == i) // removed last element queue[i] = null; else { //记录最后一个元素并将queue[s]置为null E moved = (E) queue[s]; queue[s] = null; // 从i位置开始往下遍历左右叶子结点 siftDown(i, moved); //往父节点进行遍历判断 if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; }
这里的思想就是移除目标位置的元素，然后把最后一个元素放到目标位置，进而触发向下调整。如果调整后的目标位置值等于最后一个元素，那么触发向上调整。
向下调整通常是移除元素，这样会把末尾结点拿过来填充然后触发向下调整进而使得叶子节点值小的上移到parent。向上调整通常是插入元素场景，则会遍历parent比较插入元素与parent节点值，可能使得插入元素一路向上。
