/**
	* 默認(rèn)數(shù)組長(zhǎng)度
	*/
	private static final int DEFAULT_INITIAL_CAPACITY = 11;
    /**
	 * 最大達(dá)容量，分配時(shí)超出可能會(huì)出現(xiàn) OutOfMemoryError 異常
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /**
	 * 隊(duì)列，存儲(chǔ)我們的元素
     */
    private transient Object[] queue;
    /**
     * 隊(duì)列長(zhǎng)度
     */
    private transient int size;
    /**
     * 比較器，入隊(duì)進(jìn)行權(quán)重的比較
     */
    private transient Comparator<? super E> comparator;
    /**
     * 顯示鎖
     */
    private final ReentrantLock lock;
    /**
     * 空隊(duì)列時(shí)進(jìn)行線程阻塞的 Condition 對(duì)象
     */
    private final Condition notEmpty;

/**
	* 默認(rèn)構(gòu)造，使用長(zhǎng)度為 11 的數(shù)組，比較器為空
	*/
 	public PriorityBlockingQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
	/**
	* 自定義數(shù)據(jù)長(zhǎng)度構(gòu)造，比較器為空
	*/
    public PriorityBlockingQueue(int initialCapacity) {
        this(initialCapacity, null);
    }
	/**
	* 自定義數(shù)組長(zhǎng)度，可以自定義比較器
	*/
    public PriorityBlockingQueue(int initialCapacity,
                                 Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.lock = new ReentrantLock();
        this.notEmpty = lock.newCondition();
        this.comparator = comparator;
        this.queue = new Object[initialCapacity];
    }

    public void put(E e) {
        offer(e); // never need to block
    }
 	public boolean offer(E e) {
 		//判斷是否為空
        if (e == null)
            throw new NullPointerException();
       	//顯示鎖
        final ReentrantLock lock = this.lock;
        lock.lock();
        //定義臨時(shí)對(duì)象
        int n, cap;
        Object[] array;
        //判斷數(shù)組是否滿了
        while ((n = size) >= (cap = (array = queue).length))
        	//數(shù)組擴(kuò)容
            tryGrow(array, cap);
        try {
        	//拿到比較器
            Comparator<? super E> cmp = comparator;
            //判斷是否有自定義比較器
            if (cmp == null)
            	//堆上浮
                siftUpComparable(n, e, array);
            else
            	//使用自定義比較器進(jìn)行堆上浮
                siftUpUsingComparator(n, e, array, cmp);
            //隊(duì)列長(zhǎng)度 +1
            size = n + 1;
            //喚醒休眠的出隊(duì)線程
            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) {
        	//無(wú)符號(hào)向左移，目的是找到放入位置的父節(jié)點(diǎn)
            int parent = (k - 1) >>> 1;
            //拿到父節(jié)點(diǎn)的值
            Object e = array[parent];
            //比較是否大于該元素，不大于就沒(méi)比較交換
            if (key.compareTo((T) e) >= 0)
                break;
            //以下都是元素位置交換
            array[k] = e;
            k = parent;
        }
        array[k] = key;
    }

/**
 * @Auther: Gentle
 * @Date: 2019/4/14 15:11
 * @Description: PriorityBlockingQueue 簡(jiǎn)單演示 demo 
 */
public class TestPriorityBlockingQueue {
    public static void main(String[] args) throws InterruptedException {
        PriorityBlockingQueue<Integer> concurrentLinkedQueue = new PriorityBlockingQueue<Integer>();
        concurrentLinkedQueue.offer(10);
        concurrentLinkedQueue.offer(20);
        concurrentLinkedQueue.offer(5);
        concurrentLinkedQueue.offer(1);
        concurrentLinkedQueue.offer(25);
        concurrentLinkedQueue.offer(30);
        //輸出元素排列
        concurrentLinkedQueue.stream().forEach(e-> System.out.print(e+"  "));
        //取出元素
		Integer take = concurrentLinkedQueue.take();
        System.out.println();
        concurrentLinkedQueue.stream().forEach(e-> System.out.print(e+"  "));
    }
}

public E take() throws InterruptedException {
	//顯示鎖
    final ReentrantLock lock = this.lock;
    //可中斷鎖
    lock.lockInterruptibly();
    //結(jié)果接受對(duì)象
    E result;
    try {
    	//判讀隊(duì)列是否為空
        while ( (result = dequeue()) == null)
        	//線程阻塞
            notEmpty.await();
    } finally {
        lock.unlock();
    }
    return result;
}

 private E dequeue() {
	//長(zhǎng)度減少 1
    int n = size - 1;
    //判斷隊(duì)列中是否又元素
    if (n < 0)
        return null;
    else {
    	//隊(duì)列對(duì)象
        Object[] array = queue;
        //取出第一個(gè)元素
        E result = (E) array[0];
        //拿出最后一個(gè)元素
        E x = (E) array[n];
        //置空
        array[n] = null;
        Comparator<? super E> cmp = comparator;
        if (cmp == null)
        	//下沉調(diào)整
            siftDownComparable(0, x, array, n);
        else
            siftDownUsingComparator(0, x, array, n, cmp);
       	//成功則減少隊(duì)列中的元素?cái)?shù)量
        size = n;
        return result;
    }
}

private static <T> void siftDownComparable(int k, T x, Object[] array,
                                               int n) {
    //判斷隊(duì)列長(zhǎng)度
    if (n > 0) {
        Comparable<? super T> key = (Comparable<? super T>)x;
        //找到隊(duì)列最后一個(gè)元素的父節(jié)點(diǎn)的索引。
        //如下圖最大元素是30 父節(jié)點(diǎn)是 10，對(duì)于索引是 2
        int half = n >>> 1;           // loop while a non-leaf
        while (k < half) {
        	//拿到 k 節(jié)點(diǎn)下的左子節(jié)點(diǎn)
            int child = (k << 1) + 1; // assume left child is least
            //取得子節(jié)點(diǎn)對(duì)應(yīng)的值
            Object c = array[child];
            //取得 k 右子節(jié)點(diǎn)的索引
            int right = child + 1;
            //比較右節(jié)點(diǎn)的索引是否小于隊(duì)列長(zhǎng)度和左右子節(jié)點(diǎn)的值進(jìn)行比較
            if (right < n &&
                ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
                c = array[child = right];
            //比較父節(jié)點(diǎn)值是否大于子節(jié)點(diǎn)
            if (key.compareTo((T) c) <= 0)
                break;
            //下面都是元素替換
            array[k] = c;
            k = child;
        }
        array[k] = key;
    }
}