【Java集合源碼】PriorityQueue源碼分析

1、結構體系

PriorityQueue屬于Queue集合體系，為優先隊列。隊列是一種先進先出的資料結構。而優先隊列，它的元素出隊順序與元素的優先級有關。其内部根據維護一個大根堆或小根堆，預設情況是小根堆

2、二叉堆

在了解PriorityQueue前，有必要先了解何為二叉堆。

【資料結構】二叉堆

了解PriorityQueue，首先要了解兩個最基本的操作

1. 上浮（siftUp）

   添加元素後，上浮進行二叉堆的再平衡

2. 下沉 （siftDown）

   删除元素後，下沉進行二叉堆的再平衡

3、主要參數

//預設容量大小
	private static final int DEFAULT_INITIAL_CAPACITY = 11;
    //儲存元素的數組，同樣是一個二叉堆
    transient Object[] queue; // non-private to simplify nested class access
    //集合元素數量
    private int size = 0;
	//比較器，自定義比較邏輯，決定是大根堆還是小根堆
    private final Comparator<? super E> comparator;
    //集合修改次數
    transient int modCount = 0; 
           

根據幾個成員變量，可以知曉PriorityQueue内部使用數組實作二叉堆，預設的容量大小為11

4、構造函數

//空參構造器
	public PriorityQueue() {
		//比較器為null
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
	
	//自定義初始化容量
	public PriorityQueue(int initialCapacity) {
		//比較器為null
        this(initialCapacity, null);
    }

	//自定義比較器
	public PriorityQueue(Comparator<? super E> comparator) {
		//使用預設容量
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

	//自定義容量和比較器
	public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }
           

5、add方法

public boolean add(E e) {
		//直接調用offer方法
        return offer(e);
    }
           

6、offer方法

//入隊方法
	public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        //修改次數加1
        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;
    }
           

7、grow方法

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));
        //為了防止溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
       	//元素拷貝
        queue = Arrays.copyOf(queue, newCapacity);
    }
           

擴容的本質是利用Arrays.copyOf方法進行元素複制，重點在于新數組的大小

• oldCapacity < 64 -> newCapacity = oldCapacity * 2 + 2
• oldCapacity > 64 -> newCapacity = 1.5 * oldCapacity
• newCapacity > 2147483639，newCapacity = Integer.MAX_VALUE

8、siftUp方法

private void siftUp(int k, E x) {
        if (comparator != null)
        	//使用初始化的比較器進行上浮
            siftUpUsingComparator(k, x);
        else
        	//使用預設的比較器進行上浮
            siftUpComparable(k, x);
    }
           

9、siftUpComparable方法

private void siftUpComparable(int k, E x) {
		//将對象強轉成Comparable，進而可以使用compareTo方法進行比較
        Comparable<? super E> key = (Comparable<? super E>) x;
        //k即為目前循環的子節點的下标
        while (k > 0) {
        	//計算父節點下标
            int parent = (k - 1) >>> 1;
            //擷取父節點元素
            Object e = queue[parent];
            //如果父節點元素大于子節點元素，直接結束
            if (key.compareTo((E) e) >= 0)
                break;
            //走到這，說明父節點的值小于子節點的值，進行上浮，将父節點設定成子節點的值
            //注意，這裡并沒有數組父子節點元素交換，隻是将父節點的值寫入子節點中，并再最終跳出循環後，再将
            //子節點的值寫入父節點，減少了元素交換次數
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }
           

10、poll方法

将堆頂元素出隊，并通過下沉操作使二叉堆再平衡

public E poll() {
        if (size == 0)
        	//隊列中元素總個數為0，直接傳回null結束
            return null;
        //元素總個數減一
        int s = --size;
        //集合修改次數加一
        modCount++;
        //取出要傳回的隊首元素
        E result = (E) queue[0];
        //取出要放在隊首并下沉的隊尾元素
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
        	//下沉
            siftDown(0, x);
        return result;
    }
           

11、siftDown方法

private void siftDown(int k, E x) {
 		//比較器不為null，使用比較器進行下沉
        if (comparator != null)
            siftDownUsingComparator(k, x);
        //否則，使用Comparable進行比較并下沉
        else
            siftDownComparable(k, x);
    }
           

12、siftDownComparable方法

private void siftDownComparable(int k, E x) {
 		//強轉，使用compareTo方法進行比較
        Comparable<? super E> key = (Comparable<? super 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 &&
                ((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;
    }