【BlockingQueue】PriorityBlockingQ

内部维护了lock和notEmpty两个属性
1.比较的对象必须实现comparable<T>接口，底层用数组实现，小值排左边，大值排右边
2.底层用数组实现，无界队列
3.take()方法是阻塞的，如果队列中为空， 会调用notEmpty.await()方法。
4.采用和ArrayBlockingQueue一样的独占锁，控制1次只有一个线程可以操作入队和出队，priority队列只有notEmpty,而没有notFull，因为是无界队列，会自动扩容
5.任何的put相关的队列都不会阻塞，与take相关的操作会阻塞
6.PriorityBlockingQueue始终保证出队的元素是优先级最高的元素，并且可以定制优先级的规则，内部通过使用一个二叉树最小堆算法来维护内部数组，这个数组是可扩容的，当当前元素个数>=最大容量时候会通过算法扩容
7.默认情况下元素采用自然顺序升序排序，当然我们也可以通过构造函数来指定Comparator来对元素进行排序。需要注意的是PriorityBlockingQueue不能保证同优先级元素的顺序

最小堆的构建：
1.插入
a.将元素a插入到队列尾部n处，首先与其父节点k比较，如果大于，则将a放在n处，结束
b.如果a小于父节点，则将父节点k放在n处，继续拿a与k的父节点pa比较，如果大于，则将a放在k处，结束
c.如果小于，则继续与pa的父节点pa1比较，以此类推，直到比较到堆的头部，也就是数组的下标0

2.删除
a.删除头节点a后，比较堆尾部节点k与左右子节点的大小，将小的节点提升为头节点，此时产生了空穴
b.继续比较空穴的子节点，并将小的节点放在空穴处，以此类推

队列中创建最小队的方法：
private static <T> void siftUpComparable(int k, T x, Object[] array) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    //队列元素个数>0则判断插入位置，否者直接入队(7)
    while (k > 0) {
        int parent = (k - 1) >>> 1; //父节点 (k-1)/2
        Object e = array[parent];
        if (key.compareTo((T) e) >= 0)
            break;
        array[k] = e;
        k = parent;
    }
    array[k] = key;(8)
}

调用poll等方法时，会移除队列的第一项，然后将最后一项移动到队首，并调整队的顺序：

private static <T> void siftDownComparable(int k, T x, Object[] array,
                                            int n) {
     if (n > 0) {
         Comparable<? super T> key = (Comparable<? super T>)x;
         int half = n >>> 1;           // loop while a non-leaf
         while (k < half) {
             int child = (k << 1) + 1;   //k节点的左子节点
             Object c = array[child];（5）
             int right = child + 1;（6)  //k节点的右子节点
             if (right < n &&
                 ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)(7)
                 c = array[child = right]; //取两个子节点中最小的一个值
             if (key.compareTo((T) c) <= 0)(8) //再和数组中最后一个值比较，如果小于，则将数组中最后一个位置n的值移动到队列头部k位置，否则将头部位置替换为左右子节点中较小的一个c，再比较n的值和c的大小。
                 break;
             array[k] = c;
             k = child;
         }
         array[k] = key;(9)
     }
 }

【参考博客】
http://www.importnew.com/25541.html
https://www.jianshu.com/p/43954715aa28【有二叉队的详细解释】