PriorityQueue
一個無限的優(yōu)先級隊列基于一個優(yōu)先級堆咆课。優(yōu)先級隊列中的元素根據(jù)它們的Comparable自然順序或通過在隊列構(gòu)造時提供的Comparator來排序。(如果有Comparator就根據(jù)Comparator來對元素進行排序扯俱，否則根據(jù)元素自己的Comparable來進行排序)书蚪。一個優(yōu)先級隊列不允許‘null’元素。一個依賴自然排序的優(yōu)先級隊列甚至不允許插入一個不可比較(non-comparable)的對象(如果你插入一個non-comparable對象迅栅，則會拋出一個ClassCastException異常)殊校。
隊列的頭(head)元素是相對于指定順序的最小的(least)元素。如果多個元素被綁為最小值库继，那么頭元素是它們中的一個————綁定會被任意的破壞。隊列的檢索操作poll窜醉、remove宪萄、peek和element都會訪問隊列頭(head)元素。
一個優(yōu)先級隊列是無限制的榨惰，但是它有一個內(nèi)部的“capacity”管理著數(shù)組的大小拜英，該數(shù)組用于存儲隊列的元素。它總是至少同隊列大小一樣大琅催。當元素加到優(yōu)先級隊列中居凶，它的容量會自動增加。并沒有指定增長策略的細節(jié)藤抡。
該類和它的迭代器實現(xiàn)了Collection和Iterator接口所有可選的方法侠碧。迭代器提供的iterator()方法不保證遍歷優(yōu)先級隊列的元素根據(jù)任何特別的順序。如果你需要有序的遍歷缠黍，考慮使用Arrays.sort(pq.toArray()).
注意弄兜，PriorityQueue類的實現(xiàn)是非同步的。如果任何一個線程修改隊列，多線程不應(yīng)該同時訪問一個PriorityQueue實例替饿。相反语泽，應(yīng)該使用線程安全的PriorityBlockingQueue類。
實現(xiàn)注意：該實現(xiàn)提供了O(log(n))時間復(fù)雜度對于入隊和出隊方法：offer视卢、poll踱卵、remove()和add；線性的時間O(n)對于remove(object)和contains(object)方法据过；和常量的時間O(1)對于檢索方法：peek惋砂、element和size。
屬性
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
優(yōu)先級隊列表現(xiàn)為一個平衡二項堆(即蝶俱，平衡二叉樹)：queue[n]的兩個兒子分別是queue[2n+1]和queue[2(n+1)]班利。優(yōu)先級隊列通過比較器(comparator)來排序，或者如果比較器為空則通過元素的自然順序來排序：堆中每個節(jié)點n和n的每個后裔節(jié)點d榨呆，n <= d罗标。假設(shè)隊列是非空的，那么具有最低值的元素在queue[0]积蜻。
優(yōu)先級隊列的數(shù)據(jù)結(jié)構(gòu)是一個平衡二叉樹闯割，并且數(shù)中所有的子節(jié)點必須大于等于父節(jié)點，而同一層子節(jié)點間無需維護大小關(guān)系竿拆。這樣的結(jié)構(gòu)性讓優(yōu)先級隊列看起來像是一個最小堆宙拉。
① 假設(shè)父節(jié)點為queue[n]，那么左孩子節(jié)點為queue[2n+1]丙笋，右孩子節(jié)點為queue[2(n+1)]谢澈。
② 假設(shè)孩子節(jié)點(無論是左孩子節(jié)點還是右孩子節(jié)點)為queue[n]，n>0御板。那么父節(jié)點為queue[(n-1) >>> 1]
節(jié)點間的大小關(guān)系：
① 父節(jié)點總是小于等于孩子節(jié)點
② 同一層孩子節(jié)點間的大小無需維護
葉子節(jié)點與非葉子節(jié)點：
① 一個長度為size的優(yōu)先級隊列锥忿，當index >= size >>> 1時，該節(jié)點為葉子節(jié)點怠肋。否則敬鬓，為非葉子節(jié)點。"附"中會對該結(jié)論做個簡單的證明笙各。
/**
* 優(yōu)先級隊列元素的個數(shù)
*/
private int size = 0;
/**
* 優(yōu)先級隊列結(jié)構(gòu)上被修改的次數(shù)钉答。修改操作包括：clear()、offer(E)杈抢、poll()数尿、removeAt(int)
*/
transient int modCount = 0; // non-private to simplify nested class access
方法
- 添加節(jié)點
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;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
往優(yōu)先級隊列中插入元素，如果隊列滿了惶楼，則進行擴容砌创。插入操作必要的話是會導致堆元素調(diào)整的虏缸，以滿足父節(jié)點總是小于等于子節(jié)點的要求。
插入操作的時間復(fù)雜度為O(log(n));
通過siftUp方法來完成元素插入時的調(diào)整：siftUp(index, object)方法會升高待插入元素在樹中的位置index嫩实，直到待插入的元素大于或等于它待插入位置的父節(jié)點
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) 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;
}
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
通過“int parent = (k - 1) >>> 1;”獲取到當前要插入節(jié)點位置的父節(jié)點刽辙，比較父節(jié)點和待插入節(jié)點，如果待插入節(jié)點小于父節(jié)點甲献，則將父節(jié)點插入到子節(jié)點的位置宰缤，然后在獲取父節(jié)點的父節(jié)點循環(huán)上面的操作，直到待插入節(jié)點大于等于父節(jié)點晃洒，則在相應(yīng)位置插入這個節(jié)點慨灭。最終保證代表優(yōu)先級隊列的平衡二叉樹中，所有的子節(jié)點都大于它們的父節(jié)點球及，但同一層的子節(jié)點間并不需要維護大小關(guān)系氧骤。
圖解“添加節(jié)點”步驟：
往一個空的優(yōu)先級隊列中依次插入“13”、“-3”吃引、“20”筹陵、“-25”
① 插入“13”
② 插入“-3”
③ 插入“20”
④ 插入“-25”
- 獲取優(yōu)先級隊列頭結(jié)點
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
獲取優(yōu)先級隊列頭元素，也就是優(yōu)先級隊列中值最小的元素镊尺。
獲取操作的時間復(fù)雜度為O(1)
- 刪除節(jié)點
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
該刪除操作的最壞耗時為：n + 2log(n); 所以該操作的的時間復(fù)雜度為O(n);
indexOf(object)操作時間復(fù)雜度為O(n);
removeAt(index)操作時間復(fù)雜度為O(log(n))
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
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;
}
如果待刪除節(jié)點位置為隊列尾朦佩，則直接將隊列尾位置置null。否則將隊列尾節(jié)點前插以覆蓋待刪除節(jié)點位置的節(jié)點庐氮。
當待刪除節(jié)點的位置為非葉子節(jié)點時语稠，會進行一系列的節(jié)點調(diào)整，使得隊尾節(jié)點在前插后能保證優(yōu)先級隊列數(shù)據(jù)結(jié)構(gòu)的正確性弄砍。
當待刪除節(jié)點的位置為葉子節(jié)點時仙畦，會先將隊尾節(jié)點設(shè)置到待刪除節(jié)點位置以使得隊列中已經(jīng)沒有待刪除節(jié)點了，然后再進行已經(jīng)插入到新位置的隊尾節(jié)點同它新父節(jié)點進行比較調(diào)整音婶，以保證父節(jié)點總是小于等于子節(jié)點慨畸，即保證優(yōu)先級隊列數(shù)據(jù)結(jié)構(gòu)的正確性。
當該方法進行siftUp操作來對節(jié)點進行結(jié)構(gòu)調(diào)整后使得隊尾節(jié)點最終并不是被設(shè)置到了待刪除節(jié)點位置桃熄，這時就返回這個前插的隊尾元素先口。因為這種情況下型奥，刪除操作會涉及到一個未訪問的元素被移動到了一個已經(jīng)訪問過的節(jié)點位置瞳收。在迭代器操作中需要特殊處理。
通過siftDown方法來完成元素移除時的調(diào)整：siftDown(index, object)方法會降低待插入元素在樹中的位置index厢汹，直到待插入的元素小于或等于它待插入位置的孩子節(jié)點螟深。
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
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 &&
((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;
}
@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 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;
k = child;
}
queue[k] = x;
}
因為在平衡二叉樹中，葉子節(jié)點的個數(shù)總是大于等于前面所有非葉子節(jié)點個數(shù)之和烫葬。所有如果待刪除元素的所在位置大于等于隊列長度的一半界弧，則說明待刪除的節(jié)點是一個葉子節(jié)點凡蜻，則直接將隊列中最后一個節(jié)點值(注意，隊列中最后一個節(jié)點一定也是葉子節(jié)點)設(shè)置到待刪除節(jié)點所在位置垢箕。
如果待刪除節(jié)點的位置小于隊列長度的一半划栓，則說明待刪除的節(jié)點是一個非葉子節(jié)點。那么先取得待刪除節(jié)點的子節(jié)點中小的那個子節(jié)點条获，將該子節(jié)點與隊列中最后一個節(jié)點進行比較忠荞，如果子節(jié)點小于隊列中最后一個節(jié)點，則將子節(jié)點值設(shè)置到待刪除節(jié)點的位置帅掘，然后再次獲取當前子節(jié)點的較小的子節(jié)點重復(fù)一樣的操作委煤，直到隊列最后一個節(jié)點比較小的那個子節(jié)點還要小，則將隊列最后一個節(jié)點值設(shè)置為這個子節(jié)點的父節(jié)點修档。最終保證代表優(yōu)先級隊列的平衡二叉樹中碧绞，所有的父節(jié)點都小于等于它的子節(jié)點，但同一層的子節(jié)點間并不需要維護大小關(guān)系吱窝。
圖解“刪除節(jié)點”步驟：
假設(shè)有如下優(yōu)先級隊列：
情況二：刪除“queue[2]=-23”
- 是否包含節(jié)點
public boolean contains(Object o) {
return indexOf(o) != -1;
}
判斷優(yōu)先級隊列中是否包含object對象讥邻。該方法的時間復(fù)雜度為：O(n)
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
- 移除并獲取優(yōu)先級隊列頭節(jié)點
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
移除并獲取優(yōu)先級隊列頭節(jié)點。該操作的時間復(fù)雜度為：O(log(n));
- 清除優(yōu)先級隊列中所有節(jié)點
modCount++;
for (int i = 0; i < size; i++)
queue[i] = null;
size = 0;
}
清除優(yōu)先級隊列中的所有節(jié)點癣诱。該操作的事件復(fù)雜度為：O(n);
- 迭代器
優(yōu)先級隊列的迭代器并不保證遍歷按照指定的順序獲取節(jié)點元素计维。這是因為當在迭代器中執(zhí)行remove操作時，可能會涉及到一個未訪問的元素被移動到了一個已經(jīng)訪問過的節(jié)點位置(刪除操作時撕予，當隊尾節(jié)點被放置到待移除節(jié)點位置的情況下鲫惶，需要調(diào)用siftUp方法，siftUp(index, object)方法會升高待插入元素在樹中的位置index实抡，直到待插入的元素大于或等于它待插入位置的父節(jié)點)欠母。在迭代器操作中需要特殊處理。此時這些不幸的元素會在所有節(jié)點遍歷完后才得以遍歷吆寨。
附
- 證明“在平衡二叉樹中赏淌，葉子節(jié)點的個數(shù)總是大于等于前面所有非葉子節(jié)點個數(shù)之和∽那澹”
一個平衡二叉樹第N層節(jié)點數(shù)為：2^N
一個N層的平衡二叉樹總節(jié)點數(shù)為：2^(N+1) -1六水；
Sn = 2^0 + 2^1 + …… + 2^N
2*Sn = 2^1 + 2^2 + …… + 2^N + 2^(N+1)
將二個等式的左邊和右邊分別進行相減操作得到：
(2-1)Sn = 2^(N+1) - 2^0 ==> Sn = 2^(N+1) -1;
所以一個N層的二叉平衡樹除了葉子節(jié)點外的節(jié)點總數(shù)最大為：2^N -1；
因而2^N > 2^N -1辣卒，所以在滿平衡二叉樹下掷贾，葉子節(jié)點大于非葉子節(jié)點個數(shù)之和，當然在最后一層節(jié)點不滿的情況下荣茫，葉子節(jié)點依舊大于等于所有非葉子之和想帅。
后記
若文章有任何錯誤，望大家不吝指教:)
