PriorityQueue 源碼解讀

今天看了一道算法是合并k個排序連結清單，傳回合并後得排序連結清單，其中有一種解法是通過PriorityQueue來實作得，是以就看下PriorityQueue得源碼，了解下。

基于JDK 1.8 得源碼進行分析得。

Java得PriorityQueue 實作了Queue接口，通過堆來完全二叉樹來實作最小堆，是以其底層是通過數組來實作得。

                                     圖檔來自（http://www.cnblogs.com/CarpenterLee/p/5488070.html）

通過上圖可以輕易得算出某個節點得父節點和子節點得下标，是以說為什麼可以直接用數組來存儲得原因。

Add（）方法得實作是通過offer來實作得，是以直接看下offer就可以了。

/**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }
           

首先判斷目前size是否夠用，如果不夠用，調用grow 來擴容，接着如果是空得隊列，則放在第一個位置，否則調用siftUp來調整存放得位置。看下siftUp得源碼。

  /**
     * Inserts item x at position k, maintaining heap invariant by
     * promoting x up the tree until it is greater than or equal to
     * its parent, or is the root.
     *
     * To simplify and speed up coercions and comparisons. the
     * Comparable and Comparator versions are separated into different
     * methods that are otherwise identical. (Similarly for siftDown.)
     *
     * @param k the position to fill
     * @param x the item to insert
     */
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }
           

如果是chongxie了Comparator ，則comparator 不為null ，就調用siftUpUsingComparator，否則調用siftUpComparable，接着看下siftUpUsingComparator得源碼。

 @SuppressWarnings("unchecked")
    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }
           

首先擷取到最後一個父節點得位置索引，擷取該值，然後做比較，如果滿足堆結構，則直接傳回，如果不滿足，則層層交換，知道滿足堆結構為止。siftUpComparable得實作也是差不多得，就不說了。

看下remove實作

/**
     * Removes a single instance of the specified element from this queue,
     * if it is present.  More formally, removes an element {@code e} such
     * that {@code o.equals(e)}, if this queue contains one or more such
     * elements.  Returns {@code true} if and only if this queue contained
     * the specified element (or equivalently, if this queue changed as a
     * result of the call).
     *
     * @param o element to be removed from this queue, if present
     * @return {@code true} if this queue changed as a result of the call
     */
    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }
           

主要實作得是removeAt函數；

 * Removes the ith element from queue.
     *
     * Normally this method leaves the elements at up to i-1,
     * inclusive, untouched.  Under these circumstances, it returns
     * null.  Occasionally, in order to maintain the heap invariant,
     * it must swap a later element of the list with one earlier than
     * i.  Under these circumstances, this method returns the element
     * that was previously at the end of the list and is now at some
     * position before i. This fact is used by iterator.remove so as to
     * avoid missing traversing elements.
     */
    @SuppressWarnings("unchecked")
    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);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }
        return null;
    }
           

如果删除得是最後一個索引，就直接删除，否則先擷取該值，然後直接删除，接着調整位置，先調用siftDown，看下該源碼

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

接着看下siftDownUsingComparator得實作

 @SuppressWarnings("unchecked")
    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }
           

首先擷取該索引對應得父節點得左右節點，然後對比左右節點得大小來調整堆結構。

調用完siftDown 之後，接着比較如果調整後得index對應得資料和删除得相等，由于删除操作會涉及到一個未通路的元素被移動到了一個已經通路過的節點位置，在疊代器操作中是需要特殊處理得，是以調用siftUp來調整位置隊尾節點最終并不是被設定到了待删除節點位置，這時就傳回這個前插的隊尾元素。

參考博文 ： https://cloud.tencent.com/developer/article/1152628