《徐徐道來話Java》：PriorityQueue和最小堆

在講解PriorityQueue之前，需要先熟悉一個有序資料結構：最小堆。

最小堆是一種經過排序的完全二叉樹，其中任一非終端節點數值均不大于其左孩子和右孩子節點的值。

可以得出結論，如果一棵二叉樹滿足最小堆的要求，那麼，堆頂（根節點）也就是整個序列的最小元素。

最小堆的例子如下圖所示：

可以注意到，20的兩個子節點31、21，和它們的叔節點30并沒有嚴格的大小要求。以廣度優先的方式從根節點開始周遊，可以構成序列：

[10,20,30,31,21,32,70]

反過來，可以推演出，序列構成二叉樹的公式是：對于序列中下标為i的元素，左孩子為left(i) = i*2 +1，右孩子為 right(i) = left(i)+1。

現在可以思考一個問題，對于給定的序列，如何讓它滿足最小堆的性質？

例如[20, 10, 12, 1, 7, 32, 9]，可以構成二叉樹：

這裡提供一個方法：

1、倒序周遊數列；

2、挨個進行沉降處理，沉降過程為：和左右子節點中的最小值比對，如果比最小值要大，則和該子節點交換資料，反之則不做處理，繼續1過程；

3、沉降後的節點，再次沉降，直到葉子節點。

同時，因為下标在size/2之後的節點是葉子節點，無需比對，是以可以從size/2-1位置開始倒序周遊，節約執行次數。

應用該方法對之前的數列進行解析：

1、數列[20,10,12,1,7,32,9]長度為7，是以size/2 - 1 =2，倒序周遊過程是12 -> 10 ->20；

2、12的左孩子為32，右孩子為9，12>9，進行沉降，結果如下圖所示：

3、10的左孩子為1，右孩子為7，10 > 1，進行沉降，結果如下圖所示：

4、20的左孩子為1，右孩子為9，20 > 1，進行沉降，結果如下圖所示：

5、20的左孩子為10，右孩子為7，20 > 7，進行沉降，得到最終結果：

滿足最小堆的要求，此時，得出的序列為[1,7,9,10,20,32,12]。

該實作的流程也就是PriorityQueue的heapify方法的流程，heapify方法負責把序列轉化為最小堆，也就是所謂的建堆。其源碼如下所示：

private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }      

siftDown方法也就是之前提過的沉降。

 siftDown(k,x)方法解析

siftDown這個方法，根據comparator成員變量是否為null，它的執行方式略有不同:

如果comparator不為null，調用comparator進行比較；

反之，則把元素視為Comparable進行比較;

如果元素不為Comparable的實作，則會抛出ClassCastException。

不論哪種，執行的算法是一樣的，這裡隻做Comparator的源碼解析：

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的時間複雜度不會超出O(logn)。

siftUp(k,x)方法解析

siftUp方法用于提升節點。新加入的節點一定在數列末位，為了讓數列滿足最小堆性質，需要對該節點進行提升操作。

和siftDown一樣，它也有兩種等效的實作路徑，這裡隻做shifUpUsingComparator的解析：

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

節點的插入，是在數列的尾端的，它很可能比父節點要小，不滿足最小堆的定義，是以，需要做上浮的操作。

這裡提供一個例子幫助了解，有最小堆數列[10，20，30，40，30，50，70]，構成最小堆如下所示：

1、執行添加19，變為：

2、19<40，與40交換位置：

3、19<20，與20交換位置：

4、19>10，終止上浮操作，最後得到的數列為：

[10，19，30，20，30，50，70，40]

滿足了最小堆的性質。