Java集合源碼分析——PriorityQueue和PriorityBlockQueue

PriorityQueue

PriorityQueue是基于數組結構的，可自動擴容，每次擴容1

PriorityQueue實體上是基于數組結構來存儲元素的，但是在每次添加或者删除元素之後要進行堆化

是以PriorityQueue是一個有序無界隊列，預設為最大堆

屬性

//初始數組大小預設為11
	private static final int DEFAULT_INITIAL_CAPACITY = 11;

	//真正存儲元素的數組
    transient Object[] queue; 
 	
	//隊列大小
    private int size = 0;
	
	//比較器
    private final Comparator<? super E> comparator;

	//操作次數
    transient int modCount = 0; 
           

構造方法

PriorityQueue預設是一個最小堆

如果要建立最大堆，則需要自己實作比較器

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];//初始化數
    this.comparator = comparator;//初始化比較器
}
           

入隊及擴容分析

public boolean add(E e) {
    return offer(e);
}
//添加元素
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;
  
    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);
}
           

當容量小于64時，庫容為原來的兩倍加2，否則擴容為原來的1.5倍

向上調整

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<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;//無符号右移
        Object e = queue[parent];
        //如果key大于父節點
        if (key.compareTo((E) e) >= 0)
            break;
        //父節點與目前節點進行交換
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}
           

向上調整過程：

1.首先将元素添加到隊列尾部
2.然後進行堆化，即向上調整，不斷與其父節點進行比較，将元素插入到合适位置
3.堆化時間複雜度Log2N，即添加元素的時間複雜度為Log2N
           

删除元素

//删除指定元素
public boolean remove(Object o) {
    int i = indexOf(o); //周遊元素找到下标 時間複雜度O(N)
    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; //将最後一個元素置為null
    else {
        E moved = (E) queue[s];//擷取最後一個元素
        queue[s] = null;//置為null
        siftDown(i, moved);//向下調整
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

           

向下調整

//向下調整
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;
}

           

删除指定元素時，先将元素進行删除，然後将最後一個元素放到被删除的元素位置處，再進行下沉操作

删除元素時間複雜度O(N)，向下調整時間複雜度O(Log2N）

小結

PriorityQueue是一個以數組為結構，具有動态擴充能力的無界隊列，其中數組中的元素有序，在進行添加或者删除元素之後會進行堆化，預設為最小堆

1.PriorityQueue是線程不安全的
2.常用場景：存儲的資料具有優先級
           

PriorityBlockQueue

PriorityBlockQueue是一個線程安全的基于數組的優先阻塞隊列，預設為最小堆

屬性

//預設初始值
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
 
    //安全最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //真實存儲資料的數組
    private transient Object[] queue;
	
    //比較器
    private transient Comparator<? super E> comparator;
    
    //鎖
    private final ReentrantLock lock;

    private final Condition notEmpty;
           

構造方法

public PriorityBlockingQueue(int initialCapacity,
                             Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.lock = new ReentrantLock();//設定鎖
    this.notEmpty = lock.newCondition();
    this.comparator = comparator;//比較器
    this.queue = new Object[initialCapacity];//初始化數組
}
           

入隊

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    final ReentrantLock lock = this.lock;
    lock.lock();
    int n, cap;
    Object[] array;
    while ((n = size) >= (cap = (array = queue).length))
        tryGrow(array, cap);
    try {
        Comparator<? super E> cmp = comparator;
        if (cmp == null)
            siftUpComparable(n, e, array);
        else
            siftUpUsingComparator(n, e, array, cmp);
        size = n + 1;
        notEmpty.signal();
    } finally {
        lock.unlock();
    }
    return true;
}
           

總結

PriorityQueue與PriorityBlockQueue結構、入隊、出隊操作及擴容和堆化方式一緻
PriorityBLockQueue是一個阻塞隊列，即線程安全的