Queue-PriorityQueue源碼解析

2020 年 5 月 13 日
筆記
PriorityQueue, Queue

Queue隊列通常是先進先出(FIFO)，但也有特殊的非FIFO，如本文也分析的PriorityQueue。

Queue接口

Queue接口定義的方法：

添加元素接口：

add(E e) -> 往隊列添加一個元素，如果隊列已滿拋出IllegalStateException異常。
offer(E e) -> 往隊列添加一個元素，true成功，false失敗，和add區別在與不會因為隊列已滿拋異常。

刪除元素接口：

remove() -> 刪除隊列頭元素並返回該元素，如果隊列為空拋出NoSuchElementException異常。
E poll() -> 刪除隊列頭元素並返回該元素，如果隊列為空返回null（與remove不同）。

獲取隊列頭元素接口：

E element() -> 返回隊列頭部元素（沒有刪除），如果隊列為空拋出NoSuchElementException異常。
E peek() -> 返回隊列頭部元素（沒有刪除），如果隊列為空返回null。

Queue常用的實現類

上圖中列出的是Queue平時常用的實現類：

ArrayBlockingQueue -> 有邊界的數組形式實現的阻塞隊列。
LinkedBlockingQueue -> 有邊界的鏈表形式實現的阻塞隊列。
PriorityQueue -> 無邊界的二叉堆形式實現的優先級隊列。
DelayQueue -> 無邊界的優先級形式實現的延遲隊列。

PriorityQueue

PriorityQueue是基於二叉堆形式實現的無界隊列。隊列中元素類型必須是可比較的，構造函數如果沒有傳入Comparator默認是自然排序。

PriorityQueue結構

PriorityQueue繼承了AbstractQueue，AbstractQueue實現Queue接口，即PriorityQueue擁有Queue的方法和特徵。

Object[] queue：存放隊列元素。

int DEFAULT_INITIAL_CAPACITY：默認的隊列大小，默認值為11。

int size：PriorityQueue隊列中元素個數。

int modCount：PriorityQueue隊列修改次數。

Comparator<? super E> comparator：隊列元素排序比較器。

int MAX_ARRAY_SIZE：隊列最大值(Integer.MAX_VALUE – 8)，VM的保留了8位元組的 header words。

PriorityQueue示例

package com.juc.queue;

import java.util.PriorityQueue;
/**
 * Created on 2020/5/10 23:29.
 * @author Griez
 */
public class PriorityQueueTest {
    public static final PriorityQueue<Integer> QUEUE = new PriorityQueue<>();
    public static void main(String[] args) {
        for (int i = 10; i > 0 ; i--) {
            QUEUE.offer(i);
        }
        for (int i = 0; i < 10; i++) {
            System.out.println(QUEUE.poll());
        }
    }
}

創建一個存放Integer的PriorityQueue，採用默認的自然排序。並倒序的往PriorityQueue添加10-1。然後從PriorityQueue頭部出隊列並輸出，輸出結果是1-10升序。如果是讓我們實現應該是入隊時用插敘排序好並存放在queue數組中，但是這樣實現往queue數組中添加和刪除元素移動次數是不是最優的呢？接下來我們看一下Josh Bloch, Doug Lea是怎麼樣實現的。

PriorityQueue添加元素解析

java.util.PriorityQueue#offer

public boolean offer(E e) {
    if (e == null)  //《1》不能為空
        throw new NullPointerException();
    modCount++;		// 《2》修改次數加1
    int i = size;
    if (i >= queue.length) // 默認11
        grow(i + 1); // 《3》數組擴容
    size = i + 1;
    if (i == 0)		// 《4》直接把e賦值給0下標元素（頂部元素）
        queue[0] = e;
    else
        siftUp(i, e);	// 《5》篩選頂部元素
    return true;
}

《1》添加的元素不能為空，即PriorityQueue隊列不可能存在null元素。

《2》修改次數加1。

《3》如果當前PriorityQueue元素數量大於等於數組容量需要對queue進行擴容操作。

《4》如果當前PriorityQueue為空，直接把e賦值給queue數組0下標（頂部元素）。

《5》通過二叉堆，篩選頂部元素。

java.util.PriorityQueue#grow

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    // 《1》根據現有的容量選擇增長倍數
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1)); 
    // overflow-conscious code
    // 《2》如果《1》計算出的容量比最大大，則以傳入容量為準
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

《1》根據現有的容量選擇增長倍數，如果現在的容量小於64，則容量直接增長一倍再加2；否則增長50%。

《2》如果《1》計算出的容量比最大大，則以傳入容量為準。

java.util.PriorityQueue#siftUp

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

如果構造PriorityQueue時傳有特定比較器，就按特定比較器方式設置頂部元素，否則按默認自然比較器方式設置。

java.util.PriorityQueue#siftUpComparable

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x; //《1》
    while (k > 0) {
        int parent = (k - 1) >>> 1; //《2》
        Object e = queue[parent];  //《3》
        if (key.compareTo((E) e) >= 0) //《4》
            break;
        queue[k] = e;  //《5》
        k = parent;
    }
    queue[k] = key; //《6》
}

《1》添加的元素必須是Comparable子類，可比較的。

《2》計算父節點下標。

《3》得到父節點元素。

《4》跟父節點元素作比較，如果要添加的元素大於父節點元素則退出。

《5》把父節點的元素移動到數組下標k處，然後把父節點下標賦值給k，循環《1》 – 《4》步驟。

《6》經過前面步驟最終確認需要添加的元素在queue下標，並存入數組。

添加10 – 8 該方法體現的數據結構。

添加7整個過程，用堆數據結構添加7的過程只交換了兩次數據位置。如果用插敘排序這種極端情況所有數據都需要移動。

最小二叉堆特性是根節點元素值永遠是最小的。

PriorityQueue刪除元素解析

java.util.PriorityQueue#poll

public E poll() {
    if (size == 0) //《1》
        return null;
    int s = --size; //《2》
    modCount++; //《3》
    E result = (E) queue[0];//《4》
    E x = (E) queue[s];//《5》
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);//《6》
    return result;
}

《1》如果隊列為空，返回null。

《2》隊列元素總數減1。

《3》修改次數加1。

《4》把堆頭部元素取出，後面直接返回該元素。

《5》獲取queue最後一個元素並把該位置設置null。

《6》重新篩選最小值為頭部元素。

java.util.PriorityQueue#siftDown

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

如果構造PriorityQueue時傳有特定比較器，就按特定比較器方式設置頂部元素，否則按默認自然比較器方式設置。

java.util.PriorityQueue#siftDownComparable

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1; //《1》       // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; //《2》 // assume left child is least
        Object c = queue[child];//《3》
        int right = child + 1;//《4》
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) //《5》
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)//《6》
            break;
        queue[k] = c;//《7》
        k = child;
    }
    queue[k] = key;//《8》
}

《1》無符號右移1位，取size的一半。

《2》得到二叉堆的左子節點下標。

《3》獲取左子節點元素。

《4》右子節點下標。

《5》右子節點下標小於隊列元素總數，並且左子節點元素比右子節點元素大時，把右子節點元素賦值給c，把右子節點下標賦值給child。

《6》需要交換的元素key小於或等於子節點元素c，則退出循環。

《7》把子節點c設置到queue下標為k的位置，並把child賦值給k，然後重複《1》-《6》步驟。

《8》找到key合適的位置並設置該元素。

總結

PriorityQueue使用二叉堆數據結構保證了隊列頭部元素永遠是最小的，在添加和刪除的過程元素移動次數比插敘排序插入少。隊列元素是使用數組queue保存，在多線程的情況對數組queue並發操作存在安全問題。

Tags: PriorityQueue Queue