基于优先级小顶堆的无界优先级队列。 优先级队列的元素根据其自然顺序进行排序，或根据使用哪个构造函数，由队列构造时提供的比较器进行排序。优先级队列不允许 null 元素。依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致 ClassCastException）。
此队列的头部是相对于指定排序的最小元素。如果多个元素被捆绑为最小值，则头部就是这些元素之一 – 连接被任意断开。队列检索操作轮询、删除、查看和元素访问队列头部的元素。
优先级队列是无限制的，但具有内部容量，用于控制用于存储队列中元素的数组的大小。它始终至少与队列大小一样大。当元素添加到优先级队列中时，其容量会自动增长。没有具体说明增长政策的细节。
此类及其迭代器实现 Collection 和 Iterator 接口的所有可选方法。iterator（） 方法中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用 Arrays.sort（pq.toArray（））。
请注意，此实现不是同步的。如果任何线程修改了队列，则多个线程不应同时访问 PriorityQueue 实例。请改用线程安全的 java.util.concurrent.PriorityBlockingQueue 类。
实现说明：此实现为排队和出列方法（offer、poll、remove（） 和 add）提供了 O（log（n）） 时间;remove（Object） 和 contains（Object） 方法的线性时间;以及检索方法（PEEK、元素和大小）的恒定时间。
PriorityQueue
PriorityQueue是Java中唯一一个Queue接口的直接实现，如其名字所示，优先队列，其内部支持按照一定的规则对内部元素进行排序。
PriorityQueue继承关系
先看下PriorityQueue的继承实现关系，可知其是Queue的实现类，主要使用方式是队列的基本操作，而之前讲到过Queue的基本原理，其核心是FIFO（First In First Out）原理。
Java中的PriorityQueue的实现也是符合队列的方式，不过又略有不同，却别就在于PriorityQueue的priority上，其是一个支持优先级的队列，当使用了其priority的特性的时候，则并非FIFO。
PriorityQueue的使用
案列1
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(20);queue.add(14);queue.add(21);queue.add(8);queue.add(9);
queue.add(11);queue.add(13);queue.add(10);queue.add(12);queue.add(15);
while (queue.size()>0){
Integer poll = queue.poll();
System.err.print(poll+"->");
}
上述代码做的事为往队列中放入10个int值，然后使用Queue的poll()方法依次取出，最后结果为每次取出来都是队列中最小的值，说明
了PriorityQueue内部确实是有一定顺序规则的。
案例2
// 必须实现Comparable方法，想String,数值本身即可比较
private static class Test implements Comparable<Test>{
private int a;
public Test(int a) {
this.a = a;
}
public int getA() {
return a;
}
public void setA(int a) {
this.a = a;
}
@Override
public String toString() {
return "Test{" +
"a=" + a +
'}';
}
@Override
public int compareTo(Test o) {
return 0;
}
}
public static void main(String[] args) {
PriorityQueue<Test> queue = new PriorityQueue<>();
queue.add(new Test(20));queue.add(new Test(14));queue.add(new Test(21));queue.add(new Test(8));queue.add(new Test(9));
queue.add(new Test(11));queue.add(new Test(13));queue.add(new Test(10));queue.add(new Test(12));queue.add(new Test(15));
while (queue.size()>0){
Test poll = queue.poll();
System.err.print(poll+"->");
}
}
上述代码重写了compareTo方法都返回0，即不做优先级排序。发现我们返回的顺序为Test{a=20}->Test{a=15}->Test{a=12}->Test{a=10}->Test{a=13}->Test{a=11}->Test{a=9}->Test{a=8}->Test{a=21}->Test{a=14}，和放入的顺序还是不同，所以这儿需要注意在实现Comparable接口的时候一定要按照一定的规则进行优先级排序，关于为什么取出来的顺序和放入的顺序不一致后边将从源码来分析。
案例3
//没有定义优先级的,走的是默认实现的Comparator方法
// 创建一个小顶堆的 Priority Queue
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 插入元素
priorityQueue.offer(3);
priorityQueue.offer(1);
priorityQueue.offer(4);
priorityQueue.offer(2);
// 弹出最小元素
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
//定义优先级，符合优先级的在堆顶
PriorityQueue customPriorityQueue = new PriorityQueue(
Comparator.comparing(String::length));
customPriorityQueue.offer("aaa");
customPriorityQueue.offer("aa");
customPriorityQueue.offer("aaaaaa");
customPriorityQueue.offer("aaaa");
System.out.println(customPriorityQueue);
customPriorityQueue.poll();
customPriorityQueue.poll();
System.out.println(customPriorityQueue);PriorityQueue组成
/**
* 默认容量大小，数组大小
*/
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* 优先队列用平衡二进制堆表示：queue[n] 的两个子队列分别是 queue[2*n+1] 和
* queue[2*(n+1)]。
* 优先级队列按比较器排序，如果比较器为空，则按元素的自然排序：对于堆中的每个节点 n 和 n 的每个子节点 d，n <= d。假定队列是非空的，值最小的元素在 queue[0] 中（可见是小根堆）。
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* 队列中存放了多少元素
*/
private int size = 0;
/**
* 自定义的比较规则，有该规则时优先使用，否则使用元素实现的Comparable接口方法。
*/
private final Comparator<? super E> comparator;
/**
* 队列修改次数，每次存取都算一次修改
*/
transient int modCount = 0; // non-private to simplify nested class access可以看到PriorityQueue的组成很简单，主要记住一个存放元素的数组，和一个Comparator比较器即可。
PriorityQueue操作方法
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;
//i=size，当queue为空的时候
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}首先可以看到当Queue中为空的时候，第一次放入的元素直接放在了数组的第一位，那么上边案例二中第一个放入的20就在数组的第一位。而当queue中不为空时，又使用siftUp(i, e)方法，传入的参数是队列中已有元素数量和即将要放入的新元素，现在就来看下究竟siftUp(i, e)做了什么事。
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}还记得上边提到PriorityQueue的组成，是一个存放元素的数组，和一个Comparator比较器。这儿是指当没有Comparator是使用元素类实现compareTo方法进行比较。其含义为优先使用自定义的比较规则Comparator，否则使用元素所在类实现的Comparable接口方法。
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
//为什么-1， 思考数组位置0，1，2。0是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;
}可以看到，当PriorityQueue不为空时插入一个新元素，会对其新元素进行堆排序处理（对于堆排序此处不做描述），这样每次进来都会对该元素进行堆排序运算，这样也就保证了Queue中第一个元素永远是最小的（默认规则排序）。
pool方法
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
//s = --size,即原来数组的最后一个元素
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}此处可知，当取出一个值进行了siftDown操作，传入的参数为索引0和队列中的最后一个元素。
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;
if (right < size &&
//c和right是parent的两个子节点，找出小的那个成为新的c。
((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;
}当没有Comparator比较器是采用的siftDown方法如上，因为索引0位置取出了，找索引0的子节点比它小的作为新的父节点并在循环内递归。PriorityQueue是不是很简单呢，其他细节就不再详解，待诸君深入。