英协网
我们知道线程Thread可以调用setPriority(int newPriority)来设置优先级的，线程优先级高的线程先执行，优先级低的后执行。而前面介绍的ArrayBlockingQueue、LinkedBlockingQueue都是采用FIFO原则来确定线程执行的先后顺序，那么有没有一个队列可以支持优先级呢？ PriorityBlockingQueue 。
PriorityBlockingQueue是一个支持优先级的无界阻塞队列。默认情况下元素采用自然顺序升序排序，当然我们也可以通过构造函数来指定Comparator来对元素进行排序。需要注意的是PriorityBlockingQueue不能保证同优先级元素的顺序。
二叉堆
由于PriorityBlockingQueue底层采用二叉堆来实现的，所以有必要先介绍下二叉堆。
二叉堆是一种特殊的堆，就结构性而言就是完全二叉树或者是近似完全二叉树，满足树结构性和堆序性。树机构特性就是完全二叉树应该有的结构，堆序性则是：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。它有两种表现形式：最大堆、最小堆。
最大堆：父节点的键值总是大于或等于任何一个子节点的键值（下右图）
最小堆：父节点的键值总是小于或等于任何一个子节点的键值（下走图）
二叉堆一般用数组表示，如果父节点的节点位置在n处，那么其左孩子节点为：2 * n + 1 ，其右孩子节点为2 * (n + 1)，其父节点为（n – 1） / 2 处。上左图的数组表现形式为：
二叉堆的基本结构了解了，下面来看看二叉堆的添加和删除节点。二叉堆的添加和删除相对于二叉树来说会简单很多。
添加元素
首先将要添加的元素N插添加到堆的末尾位置（在二叉堆中我们称之为空穴）。如果元素N放入空穴中而不破坏堆的序（其值大于跟父节点值（最大堆是小于父节点）），那么插入完成。否则，我们则将该元素N的节点与其父节点进行交换，然后与其新父节点进行比较直到它的父节点不在比它小（最大堆是大）或者到达根节点。
假如有如下一个二叉堆
这是一个最小堆，其父节点总是小于等于任一一个子节点。现在我们添加一个元素2。
第一步：在末尾添加一个元素2，如下：
第二步：元素2比其父节点6小，进行替换，如下：
第三步：继续与其父节点5比较，小于，替换：
第四步：继续比较其跟节点1，发现跟节点比自己小，则完成，到这里元素2插入完毕。所以整个添加元素过程可以概括为：在元素末尾插入元素，然后不断比较替换直到不能移动为止。
复杂度：Ο(logn)
删除元素
删除元素与增加元素一样，需要维护整个二叉堆的序。删除位置1的元素（数组下标0），则把最后一个元素空出来移到最前边，然后和它的两个子节点比较，如果两个子节点中较小的节点小于该节点，就将他们交换，知道两个子节点都比该元素大为止。
就上面二叉堆而言，删除的元素为元素1。
第一步：删掉元素1，元素6空出来，如下：
第二步：与其两个子节点（元素2、元素3）比较，都小，将其中较小的元素（元素2）放入到该空穴中:
第三步：继续比较两个子节点（元素5、元素7），还是都小，则将较小的元素（元素5）放入到该空穴中：!
第四步：比较其子节点（元素8），比该节点小，则元素6放入该空穴位置不会影响二叉堆的树结构，放入：
到这里整个删除操作就已经完成了。
二叉堆的添加、删除操作还是比较简单的，很容易就理解了。下面我们就参考该内容来开启PriorityBlockingQueue的源代码研究。
PriorityBlockingQueue
PriorityBlockingQueue继承AbstractQueue，实现BlockingQueue接口。
public class PriorityBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, java.io.Serializable
定义了一些属性：
内部仍然采用可重入锁ReentrantLock来实现同步机制，但是这里只有一个notEmpty的Condition，了解了ArrayBlockingQueue我们知道它定义了两个Condition，之类为何只有一个呢？原因就在于PriorityBlockingQueue是一个无界队列，插入总是会成功，除非消耗尽了资源导致服务器挂。
入列
PriorityBlockingQueue提供put()、add()、offer()方法向队列中加入元素。我们这里从put()入手：put(E e) ：将指定元素插入此优先级队列。
public void put(E e) {
offer(e); // never need to block
}
PriorityBlockingQueue是无界的，所以不可能会阻塞。内部调用offer(E e)：
siftUpComparable
当比较器comparator为null时，采用自然排序，调用siftUpComparable方法：
这段代码所表示的意思：将元素X插入到数组中，然后进行调整以保持二叉堆的特性。
siftUpUsingComparator
当比较器不为null时，采用所指定的比较器，调用siftUpUsingComparator方法：
private static <T> void siftUpUsingComparator(int k, T x, Object[] array,
Comparator<? super T> cmp) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = array[parent];
if (cmp.compare(x, (T) e) >= 0)
break;
array[k] = e;
k = parent;
}
array[k] = x;
}
扩容：tryGrow
整个添加元素的过程和上面二叉堆一模一样：先将元素添加到数组末尾，然后采用“上冒”的方式将该元素尽量往上冒。
出列
PriorityBlockingQueue提供poll()、remove()方法来执行出对操作。出对的永远都是第一个元素：array[0]。
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return dequeue();
} finally {
lock.unlock();
}
}
先获取锁，然后调用dequeue()方法：
siftDownComparable
如果比较器为null，则调用siftDownComparable来进行自然排序处理：
处理思路和二叉堆删除节点的逻辑一样：就第一个元素定义为空穴，然后把最后一个元素取出来，尝试插入到空穴位置，并与两个子节点值进行比较，如果不符合，则与其中较小的子节点进行替换，然后继续比较调整。
siftDownUsingComparator
如果指定了比较器，则采用比较器来进行调整：
PriorityBlockingQueue采用二叉堆来维护，所以整个处理过程不是很复杂，添加操作则是不断“上冒”，而删除操作则是不断“下掉”。掌握二叉堆就掌握了PriorityBlockingQueue，无论怎么变还是。对于PriorityBlockingQueue需要注意的是他是一个无界队列，所以添加操作是不会失败的，除非资源耗尽。
