摘要：滿二叉樹所有的節(jié)點都有個葉子節(jié)點，除了最后層葉子節(jié)點節(jié)點數(shù)和深度的關系第層上的節(jié)點數(shù)為第個節(jié)點的父節(jié)點左子節(jié)點右子節(jié)點參考下圖完全二叉樹有且僅有最底層葉子節(jié)點不完整就是完全二叉樹。例如把去掉最小堆父節(jié)點小于左右子節(jié)點的完全二叉樹。

按照下圖的配方，走了一遍源碼。
湊齊PriorityQueue就可以召喚神龍了。
Ler"s go go go!

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements"
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue; // non-private to simplify nested class access

沒錯這是個數(shù)組，為了更好的理解注釋的含義，請看下面↓。

滿二叉樹：

所有的節(jié)點都有2個葉子節(jié)點，除了最后層葉子節(jié)點；

節(jié)點數(shù)n和深度d的關系 n=2^d-1；

第i層上的節(jié)點數(shù)為2^(i-1)；

第n個節(jié)點的父節(jié)點：n/2,左子節(jié)點：2n,右子節(jié)點：2n+1;(參考下圖)

完全二叉樹：

有且僅有最底層葉子節(jié)點不完整就是完全二叉樹。（例如：把15去掉）

最小堆：

父節(jié)點小于左右子節(jié)點的完全二叉樹。

轉數(shù)組：

用數(shù)組來存儲二叉樹后（參見下圖）可得，根節(jié)點A[0]；左子節(jié)點a[2n+1];右子節(jié)點a[2(n+1)]，父節(jié)點a[(n-1)/2]。（n為數(shù)組下標，從0開始）

是的，優(yōu)先隊列的存儲結構大概就是這樣推演而來。

/**
 * Establishes the heap invariant (described above) in the entire tree,
 * assuming nothing about the order of the elements prior to the call.
 */
@SuppressWarnings("unchecked")
private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}

/**
 * Inserts item x at position k, maintaining heap invariant by
 * demoting x down the tree repeatedly until it is less than or
 * equal to its children or is a leaf.
 *
 * @param k the position to fill
 * @param x the item to insert
 */
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) {
    Comparable key = (Comparable)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) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1; //2n + 1,這里n是下標
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0) // 找出最小子節(jié)點
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0) // 父節(jié)點小則退出循環(huán)，否則進行替換
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

這是任意數(shù)組最小堆化的過程。如果是一個合格的最小堆，那么所有的父節(jié)點都在數(shù)組前半部分，而通過父節(jié)點又能得到左右子節(jié)點。因此源碼一上來就“size >>> 1”（相當于除以2），只需對前半部分進行循環(huán)處理，使得循環(huán)結束后所有父節(jié)點均大于左/右子節(jié)點。這里非根父節(jié)點會被多次比較到。heapify()后將得到上文所說的最小堆數(shù)組。

@SuppressWarnings("unchecked")
public E poll() {
    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;
}

poll()的核心也是siftDown，而這里的“siftDown(0, x);”與之前的“siftDown(i, (E) queue[i]);”不同的是，下標0所對應的元素本非x。也就是說，這里進行了個轉換：把最后queue[s]替換了queue[0]進行新的最小堆數(shù)組化。

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

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

如你所見，remove()也用到了siftDown()（同時還有siftUp()，下面介紹）。這里 經過siftDown后，如果queue[i] == moved則表示queue[i]的左右子節(jié)點都大于moved，即保證了i節(jié)點子樹是最小堆，但queue[i]的父節(jié)點是否小于moved卻未知，故又進行了siftUp。（圖片來自【2】）

/**
 * 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);
}
    
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
    Comparable key = (Comparable) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

@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()/siftUpUsingComparator()的方法。在新增元素時被調用。新增元素放在下標為size的位置。這里的down與up指的是被比較對象x的去向。比較后x被賦值給子節(jié)點就是down，被賦值給父節(jié)點就是up。當然你來寫的時候也可能新增時，從上到下循環(huán)遍歷。

PriorityQueue有序；不允許為null；非線程安全；（PriorityBlockingQueue線程安全）；沒有介紹的地方大抵與其他集合框架相似，如擴容機制等。

優(yōu)先隊列每次出隊的元素都是優(yōu)先級最高（權值最小）的元素,通過比較（Comparator或元素本身自然排序）決定優(yōu)先級。

記得常來復習啊~~~

更多有意思的內容，歡迎訪問筆者小站： rebey.cn

【1】【深入理解Java集合框架】深入理解Java PriorityQueue;

【2】java集合——Queue；