PriorityQueue
Java中PriorityQueue通過二叉小頂堆實(shí)現(xiàn)躬窜，可以用一棵完全二叉樹表示摘昌。本文從Queue接口函數(shù)出發(fā)哥攘，結(jié)合生動(dòng)的圖解，深入淺出地分析PriorityQueue每個(gè)操作的具體過程和時(shí)間復(fù)雜度晶伦，將讓讀者建立對(duì)PriorityQueue建立清晰而深入的認(rèn)識(shí)。
總體介紹
PriorityQueue：優(yōu)先隊(duì)列啄枕。優(yōu)先隊(duì)列的作用是能保證每次取出的元素都是隊(duì)列中權(quán)值最小的（Java的優(yōu)先隊(duì)列每次取最小元素婚陪，C++的優(yōu)先隊(duì)列每次取最大元素）。這里牽涉到了大小關(guān)系频祝，元素大小的評(píng)判可以通過元素本身的自然順序（natural ordering）泌参，也可以通過構(gòu)造時(shí)傳入的比較器（Comparator，類似于C++的仿函數(shù)）常空。
Java中PriorityQueue實(shí)現(xiàn)了Queue接口沽一，不允許放入null元素；其通過堆實(shí)現(xiàn)漓糙，具體說是通過完全二叉樹（complete binary tree）實(shí)現(xiàn)的小頂堆（任意一個(gè)非葉子節(jié)點(diǎn)的權(quán)值铣缠，都不大于其左右子節(jié)點(diǎn)的權(quán)值），也就意味著可以通過數(shù)組來作為PriorityQueue的底層實(shí)現(xiàn)昆禽。
上圖中我們給每個(gè)元素按照層序遍歷的方式進(jìn)行了編號(hào)蝗蛙，如果你足夠細(xì)心，會(huì)發(fā)現(xiàn)父節(jié)點(diǎn)和子節(jié)點(diǎn)的編號(hào)是有聯(lián)系的醉鳖，更確切的說父子節(jié)點(diǎn)的編號(hào)之間有如下關(guān)系：
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
通過上述三個(gè)公式捡硅，可以輕易計(jì)算出某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)以及子節(jié)點(diǎn)的下標(biāo)。這也就是為什么可以直接用數(shù)組來存儲(chǔ)堆的原因盗棵。
PriorityQueue的peek()和element()操作是常數(shù)時(shí)間壮韭，add()，offer()漾根，無參數(shù)的remove()以及poll()方法的時(shí)間復(fù)雜度都是log(N)泰涂。
方法剖析
add()和offer()
add(E e)和offer(E e)的語義相同，都是向優(yōu)先隊(duì)列中插入元素辐怕，只是Queue接口規(guī)定二者對(duì)插入失敗時(shí)的處理不同逼蒙，前者在插入失敗時(shí)拋出異常，后者則會(huì)返回false寄疏。對(duì)于PriorityQueue這兩個(gè)方法其實(shí)沒什么差別是牢。
新加入的元素可能會(huì)破壞小頂堆的性質(zhì)僵井，因此需要進(jìn)行必要的調(diào)整。
//offer(E e)
public boolean offer(E e) {
if (e == null)//不允許放入null元素
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//自動(dòng)擴(kuò)容
size = i + 1;
if (i == 0)//隊(duì)列原來為空驳棱，這是插入的第一個(gè)元素
queue[0] = e;
else
siftUp(i, e);//調(diào)整
return true;
}
上述代碼中批什，擴(kuò)容函數(shù)grow()類似于ArrayList里的grow()函數(shù)，就是再申請(qǐng)一個(gè)更大的數(shù)組社搅，并將原數(shù)組的元素復(fù)制過去驻债，這里不再贅述。需要注意的是siftUp(int k, E x)方法形葬，該方法用于插入元素x并維持堆的特性合呐。
//siftUp()
private void siftUp(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)//調(diào)用比較器的比較方法
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
新加入的元素x可能會(huì)破壞小頂堆的性質(zhì)，因此需要進(jìn)行調(diào)整笙以。調(diào)整的過程為：從k指定的位置開始淌实，將x逐層與當(dāng)前點(diǎn)的parent進(jìn)行比較并交換，直到滿足x >= queue[parent]為止猖腕。注意這里的比較可以是元素的自然順序拆祈，也可以是依靠比較器的順序。
element()和peek()
element()和peek()的語義完全相同倘感，都是獲取但不刪除隊(duì)首元素放坏，也就是隊(duì)列中權(quán)值最小的那個(gè)元素，二者唯一的區(qū)別是當(dāng)方法失敗時(shí)前者拋出異常侠仇，后者返回null轻姿。根據(jù)小頂堆的性質(zhì)，堆頂那個(gè)元素就是全局最小的那個(gè)逻炊；由于堆用數(shù)組表示互亮，根據(jù)下標(biāo)關(guān)系，0下標(biāo)處的那個(gè)元素既是堆頂元素余素。所以直接返回?cái)?shù)組0下標(biāo)處的那個(gè)元素即可豹休。
代碼也就非常簡(jiǎn)潔：
//peek()
public E peek() {
if (size == 0)
return null;
return (E) queue[0];//0下標(biāo)處的那個(gè)元素就是最小的那個(gè)
}
remove()和poll()
remove()和poll()方法的語義也完全相同，都是獲取并刪除隊(duì)首元素桨吊，區(qū)別是當(dāng)方法失敗時(shí)前者拋出異常威根，后者返回null。由于刪除操作會(huì)改變隊(duì)列的結(jié)構(gòu)视乐，為維護(hù)小頂堆的性質(zhì)洛搀，需要進(jìn)行必要的調(diào)整。
代碼如下：
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];//0下標(biāo)處的那個(gè)元素就是最小的那個(gè)
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);//調(diào)整
return result;
}
上述代碼首先記錄0下標(biāo)處的元素佑淀，并用最后一個(gè)元素替換0下標(biāo)位置的元素留美，之后調(diào)用siftDown()方法對(duì)堆進(jìn)行調(diào)整，最后返回原來0下標(biāo)處的那個(gè)元素（也就是最小的那個(gè)元素）。重點(diǎn)是siftDown(int k, E x)方法谎砾，該方法的作用是從k指定的位置開始逢倍，將x逐層向下與當(dāng)前點(diǎn)的左右孩子中較小的那個(gè)交換，直到x小于或等于左右孩子中的任何一個(gè)為止景图。
//siftDown()
private void siftDown(int k, E x) {
int half = size >>> 1;
while (k < half) {
//首先找到左右孩子中較小的那個(gè)较雕，記錄到c里，并用child記錄其下標(biāo)
int child = (k << 1) + 1;//leftNo = parentNo*2+1
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;//然后用c取代原來的值
k = child;
}
queue[k] = x;
}
remove(Object o)
remove(Object o)方法用于刪除隊(duì)列中跟o相等的某一個(gè)元素（如果有多個(gè)相等挚币，只刪除一個(gè)）亮蒋，該方法不是Queue接口內(nèi)的方法，而是Collection接口的方法忘晤。由于刪除操作會(huì)改變隊(duì)列結(jié)構(gòu)宛蚓，所以要進(jìn)行調(diào)整；又由于刪除元素的位置可能是任意的设塔，所以調(diào)整過程比其它函數(shù)稍加繁瑣。具體來說远舅，remove(Object o)可以分為2種情況：1. 刪除的是最后一個(gè)元素闰蛔。直接刪除即可，不需要調(diào)整图柏。2. 刪除的不是最后一個(gè)元素序六，從刪除點(diǎn)開始以最后一個(gè)元素為參照調(diào)用一次siftDown()即可。此處不再贅述蚤吹。
具體代碼如下：
//remove(Object o)
public boolean remove(Object o) {
//通過遍歷數(shù)組的方式找到第一個(gè)滿足o.equals(queue[i])元素的下標(biāo)
int i = indexOf(o);
if (i == -1)
return false;
int s = --size;
if (s == i) //情況1
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);//情況2
......
}
return true;
}
