PriorityQueue
源自java.util.PriorityQueue系谐，繼承結(jié)構(gòu)：
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractQueue<E>
java.util.PriorityQueue<E>
PriorityQueue也就是優(yōu)先隊(duì)列启泣，優(yōu)先隊(duì)列里面的元素是有序的（元素本身自然有序，或者通過Comparator能夠進(jìn)行比較），元素不允許為null值或者不可比較的值。隊(duì)列的頭是所有元素中最小的，如果有多個(gè)袄琳，則返回其中一個(gè)（任意的窿凤，即不穩(wěn)定排序）。iterator()方法返回的隊(duì)列的迭代器跨蟹，需要注意的是迭代器返回的元素是無序雳殊。PriorityQueue不是線程安全的，如果需要線程安全的隊(duì)列窗轩，可以使用PriorityBlockingQueue
代碼
優(yōu)先隊(duì)列是使用數(shù)組來實(shí)現(xiàn)的夯秃，并用來表示堆的邏輯接口。類中主要的屬性：
// 當(dāng)前節(jié)點(diǎn)的左孩子為2n+1痢艺，右孩子為2n+2
transient Object[] queue
// 隊(duì)列的大小仓洼，可以在構(gòu)造方法中傳遞
private int size = 0;
// modCount用來記錄隊(duì)列修改的次數(shù)
transient int modCount = 0;
相關(guān)方法：
add： 隊(duì)列中添加元素
public boolean add(E e) {
return offer(e);
}
可以看到直接調(diào)用的是offer方法,offer也是給隊(duì)列中添加元素：
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
//隊(duì)列擴(kuò)容，度列長度小于64直接double堤舒，大于64色建，增長50%
// 隊(duì)列的最大容量為Integer.MAX_VALUE - 8
// 多余的8個(gè)用來針對有些虛擬機(jī)需要保留額外的信息
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
// 上浮操作
siftUp(i, e);
return true;
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
// 找到父親節(jié)點(diǎn)
int parent = (k - 1) >>> 1;
Object e = queue[parent];
// 如果當(dāng)前節(jié)點(diǎn)比父親節(jié)點(diǎn)大，停止查找舌缤，表示位置是合適的
// 如果小箕戳，則繼續(xù)向上查找，并且邏輯上交換一下元素
if (key.compareTo((E) e) >= 0)
break;
// k位置放父親節(jié)點(diǎn)
queue[k] = e;
// 從父親節(jié)點(diǎn)的位置繼續(xù)向上找
k = parent;
}
queue[k] = key;
}
另一個(gè)比較關(guān)鍵的方法是poll国撵，用來從堆中彈出元素：
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
// 每次都是返回第一個(gè)元素
E result = (E) queue[0];
// 獲取最后一個(gè)元素
E x = (E) queue[s];
// 將最后一個(gè)元素置為空
queue[s] = null;
if (s != 0)
// 下沉操作陵吸，將x放在堆的頭部，然后下沉和合適的位置
siftDown(0, x);
return result;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
// 以隊(duì)列大小的一半為邊界介牙，因?yàn)槭呛妥庸?jié)點(diǎn)交換壮虫，超過一半就沒有子節(jié)點(diǎn)了
while (k < half) {
//找到孩子節(jié)點(diǎn)，如果孩子節(jié)點(diǎn)小于自己环础，就交換
// 如果兩個(gè)孩子都小于自己囚似，交換右節(jié)點(diǎn)
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;
}
