之前在A*算法演示程序的編碼過程中齿拂，發(fā)現(xiàn)javaScript并沒有原生的優(yōu)先隊(duì)列大脉，于是去Java中找到了PriorityQueue類蕾盯，研究了一下源碼。Java中的優(yōu)先隊(duì)列基于最小二叉堆實(shí)現(xiàn)敬飒。最小二叉堆具有兩個(gè)性質(zhì)：
結(jié)構(gòu)性：必須是一顆完全二叉樹，樹的插入從左到右芬位，一棵完全二叉樹的高度為小于log(N)的最大整數(shù)无拗。
堆序性：二叉樹的父節(jié)點(diǎn)必須小于兩個(gè)子節(jié)點(diǎn)。父節(jié)點(diǎn)下標(biāo)為n昧碉，兩個(gè)子節(jié)點(diǎn)下標(biāo)為2n+1和2(n+1)英染。父節(jié)點(diǎn)的值總是小于子節(jié)點(diǎn)揽惹，兩個(gè)子節(jié)點(diǎn)間大小關(guān)系不確定。
Java PriorityQueue特點(diǎn)：
不接受null值
不接受不可排序的值
線程不安全
容量沒有上限
插入和刪除元素的時(shí)間復(fù)雜度為O(log(n))
首先來看下最關(guān)鍵的兩個(gè)方法四康，siftDown(int k, E x)和siftUp(int k, E x)搪搏。這兩個(gè)方法是插入、刪除闪金、排序和初始化操作的基礎(chǔ)疯溺。兩個(gè)方法的目的都是讓節(jié)點(diǎn)k所在的子樹符合二叉堆的性質(zhì)，堆序性哎垦。區(qū)別在于囱嫩，siftDown將節(jié)點(diǎn)k作為子樹的父節(jié)點(diǎn)處理，siftUp則將節(jié)點(diǎn)k作為子樹的子節(jié)點(diǎn)處理漏设。
siftDown
private void siftDownComparable(int k, E x) { Comparablekey = (Comparable)x; int half = size >>> 1; //k) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; //如果父節(jié)點(diǎn)小于子節(jié)點(diǎn)墨闲，當(dāng)前子樹已經(jīng)滿足條件 //不需要繼續(xù) if (key.compareTo((E) c) <= 0) break; //否則，父節(jié)點(diǎn)與子節(jié)點(diǎn)對(duì)調(diào)郑口，繼續(xù)上述步驟 queue[k] = c; k = child; } queue[k] = key; }~~~關(guān)于這部分代碼损俭，比較有意思的是迭代條件`k>>1`,我們分size為奇數(shù)和偶數(shù)兩種情況來看：* 奇數(shù)：size為奇數(shù)，`half=(size-1)/2`潘酗，最后一個(gè)節(jié)點(diǎn)下標(biāo)為`size-1`杆兵，父節(jié)點(diǎn)下標(biāo)為`(size-1)/2-1`，所以`kkey = (Comparable) x;
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;
}
siftUp的代碼很容易理解仔夺，遞歸的與父節(jié)點(diǎn)比較大小琐脏，然后根據(jù)結(jié)果決定是否需要對(duì)調(diào)位置。
heapify
接下來是PriorityQueue的初始化方法中最復(fù)雜的一個(gè)缸兔，從一個(gè)無需集合(Collection)生成一個(gè)優(yōu)先隊(duì)列日裙。
private void initFromCollection(Collection c) {
initElementsFromCollection(c);
heapify();
}
initElementsFromCollection(c)方法很簡(jiǎn)單，將集合c中的數(shù)據(jù)放入隊(duì)列惰蜜，將集合c的大小賦予size屬性昂拂。而heapify()方法就是將集合c轉(zhuǎn)換為二叉堆的關(guān)鍵。
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
size>>>1的特殊性我們剛才已經(jīng)討論過了抛猖，這里看下heapify()是怎么做的格侯，從(size>>>1)-1開始向上遍歷，對(duì)每一個(gè)父節(jié)點(diǎn)财著，都要保證它所在的子樹符合條件联四，那么整棵樹都將符合條件。
add offer
向隊(duì)列中添加元素撑教，兩者代碼相同朝墩，之所以并存是因?yàn)镻riorityQueue繼承自Queue。
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
//容量不夠時(shí)伟姐，擴(kuò)容
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
這里將元素放于隊(duì)列尾部收苏，調(diào)用siftUp方法進(jìn)行調(diào)整亿卤。最壞的情況，新插入的元素比根節(jié)點(diǎn)的元素還要小鹿霸，那么siftUp要執(zhí)行到根節(jié)點(diǎn)所在的子樹排吴。
removeAt
刪除隊(duì)列中下標(biāo)為i的元素。由于要保持完整二叉樹的結(jié)構(gòu)杜跷，刪除元素后仍需要進(jìn)行重新排序傍念。
private E removeAt(int i) {
modCount++;
int s = --size;
//如果i就是最后一個(gè)節(jié)點(diǎn)的下標(biāo)，直接刪除
if (s == i)
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
