深入Java集合系列之五：PriorityQueue

深入Java集合系列之五：PriorityQueue

前言

今天繼續來分析一下PriorityQueue的源碼實現，實際上在Java集合框架中，還有ArrayDeque（一種雙端隊列），這裡就來分析一下PriorityQueue的源碼。PriorityQueue也叫優先隊列，所謂優先隊列指的就是每次從優先隊列中取出來的元素要麼是最大值（最大堆），要麼是最小值（最小堆）。我們知道，隊列是一種先進先出的數據結構，每次從隊頭出隊（移走一個元素），從隊尾插入一個元素（入隊），可以類比生活中排隊的例子就好理解了。

PriorityQueue說明

PriorityQueue底層實現的數據結構是“堆”，堆具有以下兩個性質：

任意一個節點的值總是不大於（最大堆）或者不小於（最小堆）其父節點的值；堆是一棵完全二叉樹

而優先隊列在Java中的使用的最小堆，意味著每次從隊列取出的都是最小的元素，為了更好理解源碼，有必要了解堆的一些數字規律。我們知道無論堆還是其他數據結構，最終都要采用編程語言加以實現，在Java中實現堆這種數據結構歸根結底采用的還是數組，但這個數組有點特殊，每個數組中的元素的左右孩子節點也存在該數組中，對於任意一個數組下標i，滿足：

左孩子節點的下標left(i)=2*i，右孩子節點right(i) = 2*i+1

這樣的話就可以把數據結構中復雜的樹形元素放在簡單的數組中了，只要按照上面的規律就可以很方便找到任意節點的左右孩子節點。解決完元素的存儲問題還要把數組中的元素還原為堆，這就是建堆的過程，後面的源碼也是基於同樣的思想。以每次向堆中添加一個元素為例，由於使用數組存儲，新添加的元素的下標是數組的最後一個下標值，對應到堆中就是堆中最後一個葉子節點，由於新添加元素破壞了堆的性質，所以需要對新的添加的元素做調整，使其移動到正確的位置，使得堆重新符合堆的性質。

那麼問題來了，從哪個位置開始建堆呢？我們注意到最後一個節點的父節點是擁有孩子節點的下標最大的節點，因為葉子節點沒有孩子節點，基於這點考慮我們選擇最後一個節點的父節點作為建堆的起點，對與每個節點來說，接著要做的就是調整節點的位置了，這是實現最大堆或者最小堆的關鍵，為了能形象說明建堆的過程，請參看下面的示意圖：

下面以元素｛6，5，3，1，4，8，7｝為例，說明建堆的具體過程：

如果你覺得這個過程太單調，你可以參考下面的動態圖，不過下面這個動態圖還包括堆排序的內容，只需要關注前面建堆哪個動態圖就好了。

好了，現在你應該了解了建堆的具體過程，下面的關鍵就是添加元素以及移除元素了，為了結合PriZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcml0ebXE1LTC68u1w/ejrM7SsNHV4rK/t9a1xMTayN3B9LW91LTC67fWzvbBy6GjPC9wPg0KPGgzIGlkPQ=="源碼分析">源碼分析

入隊

在分析入隊之前，我們來看看Java源碼是怎麼建堆的？

//從插入最後一個元素的父節點位置開始建堆
private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}
//在位置k插入元素x，為了保持最小堆的性質會不斷調整節點位置
private void siftDown(int k, E x) {
    if (comparator != null)
        //使用插入元素的實現的比較器調整節點位置
        siftDownUsingComparator(k, x);
    else
        //使用默認的比較器（按照自然排序規則）調整節點的位置
        siftDownComparable(k, x);
}
//具體實現調整節點位置的函數
private void siftDownComparable(int k, E x) {
    Comparable key = (Comparable)x;
    // 計算非葉子節點元素的最大位置
    int half = size >>> 1;        // loop while a non-leaf
    //如果不是葉子節點則一直循環
    while (k < half) {
        //得到k位置節點左孩子節點，假設左孩子比右孩子更小
        int child = (k << 1) + 1; // assume left child is least
        //保存左孩子節點值
        Object c = queue[child];
        //右孩子節點的位置
        int right = child + 1;
        //把左右孩子中的較小值保存在變量c中
        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;
    }
    //循環結束，k是葉子節點
    queue[k] = key;
}

ok，下面看看如何在一個最小堆中添加一個元素：

public boolean add(E e) {
    //調用offer函數
    return offer(e);
}
//siftUp之前的代碼主要確認隊列的容量不發生溢出，並保存隊列中的元素個數以及發生結構//性修改的次數
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;
}
//調用不同的比較器調整元素的位置
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}
//使用默認的比較器調整元素的位置
private void siftUpComparable(int k, E x) {
    Comparable key = (Comparable) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        //保存父節點的值
        Object e = queue[parent];
        //使用compareTo方法，如果要插入的元素小於父節點的位置則交換兩個節點的位置
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}
//調用實現的比較器進行元素位置的調整，總的過程和上面一致，就是比較的方法不同
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        //這裡是compare方法
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

為了更好理解上面代碼的執行過程，請參看下面的示意圖：

出隊

出隊就是從隊列中移除一個元素，我們看看在源碼中實現：

private E removeAt(int i) {
    assert i >= 0 && i < size;
    modCount++;
    //s是隊列的隊頭，對應到數組中就是最後一個元素
    int s = --size;
    //如果要移除的位置是最後一個位置，則把最後一個元素設為null
    if (s == i) // removed last element
        queue[i] = null;
    else {
        //保存待刪除的節點元素
        E moved = (E) queue[s];
        queue[s] = null;
        //先把最後一個元素和i位置的元素交換，之後執行下調方法
        siftDown(i, moved);
        //如果執行下調方法後位置沒變，說明該元素是該子樹的最小元素，需要執行上調方//法,保持最小堆的性質
        if (queue[i] == moved) {//位置沒變
            siftUp(i, moved);   //執行上調方法
            if (queue[i] != moved)//如果上調後i位置發生改變則返回該元素
                return moved;
        }
    }
    return null;
}

在上面的代碼上調方法與下調方法只會執行其中的一個，參看下面需要執行下調方法的示意圖：

這是需要執行上調方法的示意圖：

PriorityQueue小結

經過上面的源碼的分析，對PriorityQueue的總結如下：

時間復雜度：remove()方法和add()方法時間復雜度為O(logn)，remove(Object obj)和contains()方法需要O(n)時間復雜度，取隊頭則需要O(1)時間 在初始化階段會執行建堆函數，最終建立的是最小堆，每次出隊和入隊操作不能保證隊列元素的有序性，只能保證隊頭元素和新插入元素的有序性，如果需要有序輸出隊列中的元素，則只要調用Arrays.sort()方法即可 可以使用Iterator的迭代器方法輸出隊列中元素 PriorityQueue是非同步的，要實現同步需要調用java.util.concurrent包下的PriorityBlockingQueue類來實現同步 在隊列中不允許使用null元素