【jdk1.8】PriorityQueue源碼分析

#優先級隊列内部維護了一個堆的資料結構      

1. 成員變量

/**
     *  底層維護一個數組，其中queue[n]的左右兩個孩子分别是
     *  queue[2*n+1]和queue[2*(n+1)]（因為是從零開始的）。
     *  最高優先級即比較後最小的元素在隊首queue[0]。
     */
    transient Object[] queue; 

    /**
     * 優先級隊列中元素的個數。
     */
    private int size = 0;

    /**
     * 用來比較優先級的比較器。若為空，則采用元素的自然順序。
     * 比如數字的大小和字元串的字典序等。
     */
    private final Comparator<? super E> comparator;

    /**
     * 優先級隊列結構修改的次數。
     * 主要用于iterator來判斷是否并發修改而需要抛出
     * ConcurrentModificationException異常。
     */
    transient int modCount = 0;
           

2. 入隊方法

1. public boolean offer(E e)

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        //修改次數增加
        modCount++;
        //新增元素在該位置
        int i = size;
        //如果越界，則需要擴容
        //如果容量比較小（門檻值64）則加倍，否則加50%。
        if (i >= queue.length)
            grow(i + 1);
        //元素個數增加
        size = i + 1;
        //隊列為空
        if (i == 0)
            queue[0] = e;
        //元素加在末尾而向上調整
        else
            siftUp(i, e);
        return true;
    }
           

2.private void siftUp(int k, E x)

private void siftUp(int k, E x) {
    	//使用比較器
        if (comparator != null)
            siftUpUsingComparator(k, x);
    	//如果沒有比較器則使用自然序
        else
            siftUpComparable(k, x);
    }

    @SuppressWarnings("unchecked")
    private void siftUpComparable(int k, E x) {
    	//key是即将要插入的資料
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
        	//雙親節點序号，減去一因為從零開始
            int parent = (k - 1) >>> 1;
            //儲存雙親節點的值
            Object e = queue[parent];
            //如果待插入節點優先級沒有雙親節點高，說明已經該位置就是合适的插入位置
            if (key.compareTo((E) e) >= 0)//大于等于0應該往後排，即優先級低
                break;
            //如果優先級比雙親節點高，雙親節點往後排
            queue[k] = e;
            //往上調整，雙親的位置成了目前位置
            k = parent;
        }
        //将待插入的元素插入到合适位置
        queue[k] = key;
    }
           

3. 出隊方法

1. public E poll()

@SuppressWarnings("unchecked")
    public E poll() {
    	//隊列為空傳回null
        if (size == 0)
            return null;
        //元素個數減少，找出隊尾序号
        int s = --size;
        //修改次數增加
        modCount++;
        //保留隊首元素
        E result = (E) queue[0];
        //保留隊尾元素
        E x = (E) queue[s];
        //将隊尾置空
        queue[s] = null;
        //如果隊列非空，将隊尾元素放到隊首，則向下調整
        if (s != 0)
            siftDown(0, x);
        //傳回隊首元素
        return result;
    }
           

2. private void siftDown(int k, E x)

private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

    @SuppressWarnings("unchecked")
    private void siftDownComparable(int k, E x) {
    	//key為待調整元素
        Comparable<? super E> key = (Comparable<? super E>)x;
        //一半的地方
        int half = size >>> 1;        // loop while a non-leaf
        //當非葉節點，循環
        while (k < half) {
        	//待調整孩子序号，預設左孩子序号
            int child = (k << 1) + 1; // assume left child is least
            //待調整孩子，預設左孩子
            Object c = queue[child];
            //右孩子序号
            int right = child + 1;
            //如果右孩子存在，且右孩子優先級高
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            	//應該與右孩子的位置調整
                c = queue[child = right];
            //如果待調整元素優先級高，則說明已經找到了合适的位置
            if (key.compareTo((E) c) <= 0)
                break;
            //如果key優先級低，那麼c應該往前面交換
            queue[k] = c;
            //孩子節點變成目前節點，即往下調整
            k = child;
        }
        //将待調整的元素插入到合适的位置
        queue[k] = key;
    }
           

4. 移除指定位置元素的方法

private E removeAt(int i) {
        // assert i >= 0 && i < size;
    	//修改次數增加
        modCount++;
        //元素個數減少，找出隊尾的序号
        int s = --size;
        //如果待移除元素位于隊尾，直接移除
        if (s == i) // removed last element
            queue[i] = null;
        //位于隊中
        else {
        	//保留隊尾元素
            E moved = (E) queue[s];
            queue[s] = null;
            //将隊尾元素交換到删除的位置，向下調整
            siftDown(i, moved);
            /**此一情況偶爾出現，出現在調用iterator.remove的時候*/
            //當調整完之後還位于待删除的地方，則說明隊尾元素的優先級可能還要更高
            if (queue[i] == moved) {
            	//向上調整
                siftUp(i, moved);
                //如果上浮了，傳回隊尾元素
                if (queue[i] != moved)
                    return moved;
            }
        }
        //其他情況傳回空
        return null;
    }