前言
在前面一个小节中我们深入学习了LinkedList，并且从LinkedList的结构图中得知，LinkedList实现了Queue接口，今天这一小节，主要来学习Queue接口的另外一个实现，PriorityQueue，也就是优先队列，所谓的优先队列，就是在队列中根据某一个特征值自动进行排序，优先队列分为两种，最大优先队列和最小优先队列，优先队列的一个最大特性就是，当插入元素或者删除元素的时候，队列会自动进行调整，保证队首元素一定是优先权最大/最小。正是由于优先队列的这种特性，优先队列可以被用在很多地方，比如作业调度，进程调度等。
堆与堆排序
在深入学习优先队列之前，我们必须先来学习堆这一种数据结构，因为优先队列的内部正是采用堆这一种数据结构来实现的，并且，在进行操行的时候，时刻进行堆的维护，所以接下来我们先来学习堆以及堆的操作，然后顺便学习一个优秀的排序算法，堆排序，最后再深入学习优先队列
比较常用的一种堆结构是二叉堆，二叉堆的实质是一个二叉树，只不过这个二叉树有点特殊，每一个父子节点都是其子孙节点中的最大值，称之为最大堆，反之则称之为最小堆，下面采用最大堆来演示，最小堆原理相同，二叉堆一般采用数组来进行维护即可，并且，由于其本身的特性，可以得出结论，堆的左孩子索引为 i * 2， 右孩子索引为 i * 2 + 1,其中i为父亲节点的索引
接下来我们来看一下一个简单的二叉堆
从图中可以看到，每一个父子节点的值都比其子孙节点大，也就是说，根节点的值是整个堆中的值最大的一个，这就是最大堆名字的由来了
建立二叉堆的方法非常简单，根据二叉堆的特性，只需要对每个元素执行调整即可，调整的具体过程为，从后往前调整，如果发现一个元素的值比其孩子节点(左右孩子)的值小，则跟其进行交换，并且递归其发生交换的孩子，继续进行判断，交换，直至到达第一个元素，不过这里有一个可以提高效率的地方，由于叶子节点没有孩子，所以叶子节点是不需要进行交换的，具体的为，从元素个数/2开始即可，具体原因可自行学习
接下来我们来看下二叉堆的具体实现
class Heap{
private int[] data;
private int heapSize;
public Heap(int[] data, int heapSize) {
this.data = data;
this.heapSize = heapSize;
buildHeap();
}
// 建立二叉堆
private void buildHeap(){
// 从索引为堆大小/2 开始，调整元素的位置
for (int i = heapSize/2; i >= 1; i--){
heap(i);
}
}
// 建立二叉堆的具体实现
private void heap(int i){
int left = i << 1; // 左孩子索引
int right = left + 1; // 右孩子索引
int max = i;
// 如果左孩子的值比父亲的值大，则记录下左孩子索引
if (left < heapSize && data[left] > data[i]){
max = left;
}
// 如果右孩子的值比当前的最大值大，则记录下其索引
if (right < heapSize && data[right] > data[max]){
max = right;
}
// 如果孩子的值比父亲大，则进行交换
// 否则，则结束，表明已经是最大堆了
if (max != i){
int tmp = data[i];
data[i] = data[max];
data[max] = tmp;
// 递归发生交换的孩子节点
heap(max);
}
}
}
从上面可以看到，建立二叉堆是比较简单的，接下来我们来学习堆的一个应用，堆排序，堆排序是根据堆的这种特性而出现的一种排序算法，算法的流程为，首先建立二叉堆，然后每次交换第一个元素(也就是当前的最大值)与最后一个元素，调整堆，将堆的大小-1，重复上面的操作，直至堆大小为1，具体代码如下所示
// 堆排序
public void sort(){
// 建立堆
buildHeap();
while (heapSize >= 2){
// 将第一个元素与最后一个元素交换
int tmp = data[heapSize];
data[heapSize] = data[1];
data[1] = tmp;
// 堆大小-1
heapSize --;
// 从根节点调整堆，使其重新成为最大堆
heap(1);
}
}
优先队列源码剖析
首先来看下PriorityQueue的结构
从上图中可以看到，PriorityQueue继承自AbstractQueue，不过由于AbstractQueue中没有新增其他的方法，所以这里不打算进行展开，同时，由于其他的接口/抽象类我们在前面两个小节中均已经学习过了，所以这里就不进行展开了，直接来学习PriorityQueue的源码
首先是构造方法
// 无参构造器，默认大小为11
public PriorityQueue() {
// DEFAULT_INITIAL_CAPACITY = 11;
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 指定大小的构造器
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
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new