2.11 PriorityQueue使用與原始碼決議

2.11 PriorityQueue

先看下PriorityQueue的繼承實作關系，可知其是Queue的實作類，主要使用方式是佇列的基本操作，而之前講到過Queue的基本原理，其核心是FIFO（First In First Out）原理，
Java中的PriorityQueue的實作也是符合佇列的方式，不過又略有不同，卻別就在于PriorityQueue的priority上，其是一個支持優先級的佇列，當使用了其priority的特性的時候，則并非FIFO，

2.11.1 PriorityQueue的使用

案列1：

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(20);queue.add(14);queue.add(21);queue.add(8);queue.add(9);
queue.add(11);queue.add(13);queue.add(10);queue.add(12);queue.add(15);
while (queue.size()>0){
    Integer poll = queue.poll();
    System.err.print(poll+"->");
}

上述代碼做的事為往佇列中放入10個int值，然后使用Queue的poll()方法依次取出，最后結果為每次取出來都是佇列中最小的值，說明
了PriorityQueue內部確實是有一定順序規則的，

案例2：

// 必須實作Comparable方法，想String,數值本身即可比較
private static class Test implements Comparable<Test>{
    private int a;
    public Test(int a) {
        this.a = a;
    }
    public int getA() {
        return a;
    }
    public void setA(int a) {
        this.a = a;
    }
    @Override
    public String toString() {
        return "Test{" +
                "a=" + a +
                '}';
    }

    @Override
    public int compareTo(Test o) {
        return 0;
    }
}

public static void main(String[] args) {
    PriorityQueue<Test> queue = new PriorityQueue<>();
    queue.add(new Test(20));queue.add(new Test(14));queue.add(new Test(21));queue.add(new Test(8));queue.add(new Test(9));
    queue.add(new Test(11));queue.add(new Test(13));queue.add(new Test(10));queue.add(new Test(12));queue.add(new Test(15));
    while (queue.size()>0){
        Test poll = queue.poll();
        System.err.print(poll+"->");
    }
}

上述代碼重寫了compareTo方法都回傳0，即不做優先級排序，發現我們回傳的順序為Test{a=20}->Test{a=15}->Test{a=12}->Test{a=10}->Test{a=13}->Test{a=11}->Test{a=9}->Test{a=8}->Test{a=21}->Test{a=14}，和放入的順序還是不同，所以這兒需要注意在實作Comparable介面的時候一定要按照一定的規則進行優先級排序，關于為什么取出來的順序和放入的順序不一致后邊將從原始碼來分析，

2.11.2 PriorityQueue原始碼決議

組成

/**
 * 默認容量大小，陣列大小
 */
private static final int DEFAULT_INITIAL_CAPACITY = 11;

/**
 * 存放元素的陣列
 */
transient Object[] queue; // non-private to simplify nested class access

/**
 * 佇列中存放了多少元素
 */
private int size = 0;

/**
 * 自定義的比較規則，有該規則時優先使用，否則使用元素實作的Comparable介面方法，
 */
private final Comparator<? super E> comparator;

/**
 * 佇列修改次數，每次存取都算一次修改
 */
transient int modCount = 0; // non-private to simplify nested class access

可以看到PriorityQueue的組成很簡單，主要記住一個存放元素的陣列，和一個Comparator比較器即可，

offer方法原理

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;
    //i=size，當queue為空的時候
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

首先可以看到當Queue中為空的時候，第一次放入的元素直接放在了陣列的第一位，那么上邊案例二中第一個放入的20就在陣列的第一位，而當queue中不為空時，又使用siftUp(i, e)方法，傳入的引數是佇列中已有元素數量和即將要放入的新元素，現在就來看下究竟siftUp(i, e)做了什么事，

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

還記得上邊提到PriorityQueue的組成，是一個存放元素的陣列，和一個Comparator比較器，這兒是指當沒有Comparator是使用元素類實作compareTo方法進行比較，其含義為優先使用自定義的比較規則Comparator，否則使用元素所在類實作的Comparable介面方法，

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
    	//為什么-1， 思考陣列位置0，1，2， 0是1和2的父節點
        int parent = (k - 1) >>> 1;
        //父節點
        Object e = queue[parent];
        //當傳入的新節點大于父節點則不做處理，否則二者交換
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

可以看到，當PriorityQueue不為空時插入一個新元素，會對其新元素進行堆排序處理（對于堆排序此處不做描述），這樣每次進來都會對該元素進行堆排序運算，這樣也就保證了Queue中第一個元素永遠是最小的（默認規則排序），

佇列取出方法pool

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    //s = --size,即原來陣列的最后一個元素
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}

此處可知，當取出一個值進行了siftDown操作，傳入的引數為索引0和佇列中的最后一個元素，

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 &&
        	//c和right是parent的兩個子節點，找出小的那個成為新的c，
            ((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;
}

當沒有Comparator比較器是采用的siftDown方法如上，因為索引0位置取出了，找索引0的子節點比它小的作為新的父節點并在回圈內遞回，PriorityQueue是不是很簡單呢，其他細節就不再詳解，待諸君深入，