java集合之PriorityQueue

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable      

1,内部使用數組實作的二叉堆存儲元素,初始容量為11.

2,通過比較器進行排序.保證堆頂永遠為權值最小的元素.

3,add()和offer(),在PriorityQueue裡是一樣的

在數組末尾增加元素,然後用siftUpComparable()調整,小于父節點就交換.

private void siftUpComparable(int var1, E var2) {
    Comparable var3;
    int var4;
    for(var3 = (Comparable)var2; var1 > 0; var1 = var4) {
        var4 = var1 - 1 >>> 1;   //父節點的下标
        Object var5 = this.queue[var4];
        if(var3.compareTo(var5) >= 0) {
            break;
        }
        this.queue[var1] = var5;
    }
    this.queue[var1] = var3;
}      

4,poll(),取出堆頂元素,然後siftDownComparable()進行調整,将權值最小的元素調整到堆頂

private void siftDownComparable(int var1, E var2) {
    Comparable var3 = (Comparable)var2;

    int var5;
    for(int var4 = this.size >>> 1; var1 < var4; var1 = var5) {
        var5 = (var1 << 1) + 1;
        Object var6 = this.queue[var5];
        int var7 = var5 + 1;
        if(var7 < this.size && ((Comparable)var6).compareTo(this.queue[var7]) > 0) {
            var5 = var7;
            var6 = this.queue[var7];
        }

        if(var3.compareTo(var6) <= 0) {
            break;
        }

        this.queue[var1] = var6;
    }

    this.queue[var1] = var3;
}      

5,裡面有順序疊代器Iterator和并行疊代器Spliterator(java 8新增)