PriorityBlockingQueue优先队列的二叉堆实现

    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;
    } 

//新元素堆内上浮实现

    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;
        }
    }

//空元素堆内下沉实现
    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  half最后一个有子节点的父节点下标
            while (k < half) { 
                int child = (k << 1) + 1; // assume left child is least
                Object c = array[child];
                int right = child + 1;
                if (right < n
                        && ((Comparable<? super T>) c)
                                .compareTo((T) array[right]) > 0)
                    c = array[child = right];  //比较出左右子节点更小的那个子节点
                if (key.compareTo((T) c) <= 0) //如果左右子节点的最小值大于数组末尾的值，那么数组末尾的值直接放到父节点，空节点下沉结束
                    break;
                array[k] = c; // 如果子节点最小值小于数据末尾的值，子节点上浮到父空节点
                k = child; //空节点下滑到最小子节点的位置
            }
            array[k] = key; // 最后空节点填充数组最后的值
        }
    }