Queue常用類解析之PriorityQueue

PriorityQueue稱作優先隊列，與普通隊列先進先出不同，優先級隊列中優先級最高的元素最先出列。

一、屬性

//預設容量，初始化隊列沒有穿容量參數時使用
private static final int DEFAULT_INITIAL_CAPACITY = 11;

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

 /**
  * The number of elements in the priority queue.
  */
  //元素數量
 private int size = 0;

 /**
  * The comparator, or null if priority queue uses elements'
  * natural ordering.
  */
  //優先級的比較器，僅當元素為Comparable時可以為null
 private final Comparator<? super E> comparator;

 /**
  * The number of times this priority queue has been
  * <i>structurally modified</i>.  See AbstractList for gory details.
  */
  //修改次數
 transient int modCount = 0; // non-private to simplify nested class access
           

隊列的元素儲存在數組queue中，其資料結構為最小堆，也就是用數組表示的完全二叉樹。

對于下标為i的元素，其子節點的元素的下标為 2i +1 和 2i + 2，其父節點的元素的下标為 (i - 1)/2。

根據堆的特性，隊列的頭元素就是queue[0]，也就是隊列中的最小值，可以了解為優先級最高。

是以，PriorityQueue的關鍵就是對節點操作（插入和删除）後如何保持堆的特性。

二、 插入元素

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 grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}
           

// Double size if small; else grow by 50%

四、 删除元素

public boolean remove(Object o) {
	//找到元素下标
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}
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;
}
           

五、上浮

siftUpUsingComparator基于comparator屬性進行大小比較。

siftUpComparable在comparator為null時根據元素自身進行排序，要求元素必須是Comparable類型。

其餘方面，兩者沒有差别。優先使用siftUpUsingComparator進行比較。

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

元素x大于或等于父節點，符合堆特性，完成。

元素x小于父節點，節點交換，繼續向上比較。

六、下沉

siftDownUsingComparator基于comparator屬性進行大小比較。

siftDownComparable在comparator為null時根據元素自身進行排序，要求元素必須是Comparable類型。

其餘方面，兩者沒有差别。優先使用siftDownUsingComparator進行比較。

private void siftDownComparable(int k, E x) {
    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;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}
           

元素x小于或等于子節點，符合堆特性，完成。

元素x大于父節點，與子節點中最小的節點交換，繼續向下比較。