????PriorityBlockingQueue是一個(gè)支持優(yōu)先級的無界阻塞隊(duì)列，基于數(shù)組的二叉堆，其實(shí)就是線程安全的PriorityQueue。

????指定元素排序的規(guī)則有兩種方式：
????傳入PriorityBlockingQueue中的元素實(shí)現(xiàn)Comparable接口，自定義compareTo方法。
????初始化PriorityBlockingQueue時(shí)，指定構(gòu)造參數(shù)Comparator，自定義compare方法來對元素進(jìn)行排序。

????需要注意的是如果兩個(gè)對象的優(yōu)先級相同，此隊(duì)列并不保證它們之間的順序。
????PriorityBlocking可以傳入一個(gè)初始容量，其實(shí)也就是底層數(shù)組的最小容量，之后會(huì)使用tryGrow擴(kuò)容。

入隊(duì)API

// 此方法由于隊(duì)列大小沒有限制，永遠(yuǎn)不會(huì)返回false
public boolean add(E e) {
        return offer(e);
    }


public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        int n, cap;
        Object[] array;
        // 元素?cái)?shù)量超過了隊(duì)列的長度，擴(kuò)容
        while ((n = size) >= (cap = (array = queue).length))
            tryGrow(array, cap);
        try {
            Comparator<? super E> cmp = comparator;
            // 如果沒有指定比較器，則用自然順序把新元素插入到隊(duì)列
            if (cmp == null)
                siftUpComparable(n, e, array);
            // 指定了比較器，則用自定義的比較器把新元素插入到隊(duì)列
            else
                siftUpUsingComparator(n, e, array, cmp);
            // 加隊(duì)列長度
            size = n + 1;
             // 喚醒因?yàn)殛?duì)列空了，導(dǎo)致出隊(duì)阻塞的線程
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
        return true;
    }

// 沒有指定比較器調(diào)用的方法
private static <T> void siftUpComparable(int k, T x, Object[] array) {
        // 設(shè)置一個(gè)自然比較器
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
             // 找到二叉樹的父節(jié)點(diǎn)位置
            int parent = (k - 1) >>> 1;
            // 取出父節(jié)點(diǎn)的元素
            Object e = array[parent];
            // 直到要插入的元素比父節(jié)點(diǎn)大，退出。說明找到了新節(jié)點(diǎn)插入的位置
            if (key.compareTo((T) e) >= 0)
                break;
            // 把父節(jié)點(diǎn)下移
            array[k] = e;
           // k的值設(shè)置為父節(jié)點(diǎn)的值，繼續(xù)找該插入的位置，直到找到位置，
          // 或者要插入的位置是根節(jié)點(diǎn)結(jié)束
            k = parent;
        }
        // 把元素插入到相應(yīng)位置
        array[k] = key;
    }
 
// 指定比較器了調(diào)用的方法
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;
    }

出隊(duì)API

public E poll() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return dequeue();
        } finally {
            lock.unlock();
        }
    }

private E dequeue() {
        int n = size - 1;
        if (n < 0)
            return null;
        else {
            Object[] array = queue;
            E result = (E) array[0];
            E x = (E) array[n];
            array[n] = null;
            Comparator<? super E> cmp = comparator;
            if (cmp == null)
                siftDownComparable(0, x, array, n);
            else
                siftDownUsingComparator(0, x, array, n, cmp);
            size = n;
            return result;
        }
    }

       // 在k位置處添加節(jié)點(diǎn)
    private static <T> void siftDownComparable(int k, T x, Object[] array,
                                               int n) {
        if (n > 0) {
            Comparable<? super T> key = (Comparable<? super T>)x;
            // 二叉堆有一個(gè)性質(zhì)，最后一層葉子最多 占 1 / 2
            int half = n >>> 1;           // loop while a non-leaf
            // 循環(huán)非葉子節(jié)點(diǎn)
            while (k < half) {
                // 左孩子
                int child = (k << 1) + 1; // assume left child is least
                Object c = array[child];
                // 右孩子
                int right = child + 1;
                // 始終用左孩子c表示最小的數(shù)
                if (right < n &&
                    ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
                    // 這里如果右孩子小，更新child = right
                    c = array[child = right];
                // 如果當(dāng)前的k比左孩子還要小，那就不必交換了，待在那正好！
                if (key.compareTo((T) c) <= 0)
                    break;
                // 小的數(shù)向上移，k向下更新
                array[k] = c;
                k = child;
            }
            // 退出循環(huán)時(shí)，一定找到了x覆蓋的位置，覆蓋即可
            array[k] = key;
        }
    }