JUC下的阻塞队列-PriorityBlockingQueue

    PriorityBlockingQueue是一个支持优先级的无界阻塞队列，基于数组的二叉堆，其实就是线程安全的PriorityQueue。

    指定元素排序的规则有两种方式：
    传入PriorityBlockingQueue中的元素实现Comparable接口，自定义compareTo方法。
    初始化PriorityBlockingQueue时，指定构造参数Comparator，自定义compare方法来对元素进行排序。

    需要注意的是如果两个对象的优先级相同，此队列并不保证它们之间的顺序。
    PriorityBlocking可以传入一个初始容量，其实也就是底层数组的最小容量，之后会使用tryGrow扩容。

入队API

// 此方法由于队列大小没有限制，永远不会返回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;
        // 元素数量超过了队列的长度，扩容
        while ((n = size) >= (cap = (array = queue).length))
            tryGrow(array, cap);
        try {
            Comparator<? super E> cmp = comparator;
            // 如果没有指定比较器，则用自然顺序把新元素插入到队列
            if (cmp == null)
                siftUpComparable(n, e, array);
            // 指定了比较器，则用自定义的比较器把新元素插入到队列
            else
                siftUpUsingComparator(n, e, array, cmp);
            // 加队列长度
            size = n + 1;
             // 唤醒因为队列空了，导致出队阻塞的线程
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
        return true;
    }

// 没有指定比较器调用的方法
private static <T> void siftUpComparable(int k, T x, Object[] array) {
        // 设置一个自然比较器
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
             // 找到二叉树的父节点位置
            int parent = (k - 1) >>> 1;
            // 取出父节点的元素
            Object e = array[parent];
            // 直到要插入的元素比父节点大，退出。说明找到了新节点插入的位置
            if (key.compareTo((T) e) >= 0)
                break;
            // 把父节点下移
            array[k] = e;
           // k的值设置为父节点的值，继续找该插入的位置，直到找到位置，
          // 或者要插入的位置是根节点结束
            k = parent;
        }
        // 把元素插入到相应位置
        array[k] = key;
    }
 
// 指定比较器了调用的方法
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;
    }

出队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位置处添加节点
    private static <T> void siftDownComparable(int k, T x, Object[] array,
                                               int n) {
        if (n > 0) {
            Comparable<? super T> key = (Comparable<? super T>)x;
            // 二叉堆有一个性质，最后一层叶子最多 占 1 / 2
            int half = n >>> 1;           // loop while a non-leaf
            // 循环非叶子节点
            while (k < half) {
                // 左孩子
                int child = (k << 1) + 1; // assume left child is least
                Object c = array[child];
                // 右孩子
                int right = child + 1;
                // 始终用左孩子c表示最小的数
                if (right < n &&
                    ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
                    // 这里如果右孩子小，更新child = right
                    c = array[child = right];
                // 如果当前的k比左孩子还要小，那就不必交换了，待在那正好！
                if (key.compareTo((T) c) <= 0)
                    break;
                // 小的数向上移，k向下更新
                array[k] = c;
                k = child;
            }
            // 退出循环时，一定找到了x覆盖的位置，覆盖即可
            array[k] = key;
        }
    }