PriorityQueue
一個(gè)無(wú)限的優(yōu)先級(jí)隊(duì)列基于一個(gè)優(yōu)先級(jí)堆。優(yōu)先級(jí)隊(duì)列中的元素根據(jù)它們的Comparable自然順序或通過(guò)在隊(duì)列構(gòu)造時(shí)提供的Comparator來(lái)排序。(如果有Comparator就根據(jù)Comparator來(lái)對(duì)元素進(jìn)行排序，否則根據(jù)元素自己的Comparable來(lái)進(jìn)行排序)。一個(gè)優(yōu)先級(jí)隊(duì)列不允許‘null’元素。一個(gè)依賴自然排序的優(yōu)先級(jí)隊(duì)列甚至不允許插入一個(gè)不可比較(non-comparable)的對(duì)象(如果你插入一個(gè)non-comparable對(duì)象，則會(huì)拋出一個(gè)ClassCastException異常)。
隊(duì)列的頭(head)元素是相對(duì)于指定順序的最小的(least)元素。如果多個(gè)元素被綁為最小值，那么頭元素是它們中的一個(gè)————綁定會(huì)被任意的破壞。隊(duì)列的檢索操作poll、remove、peek和element都會(huì)訪問(wèn)隊(duì)列頭(head)元素。
一個(gè)優(yōu)先級(jí)隊(duì)列是無(wú)限制的，但是它有一個(gè)內(nèi)部的“capacity”管理著數(shù)組的大小，該數(shù)組用于存儲(chǔ)隊(duì)列的元素。它總是至少同隊(duì)列大小一樣大。當(dāng)元素加到優(yōu)先級(jí)隊(duì)列中，它的容量會(huì)自動(dòng)增加。并沒(méi)有指定增長(zhǎng)策略的細(xì)節(jié)。
該類和它的迭代器實(shí)現(xiàn)了Collection和Iterator接口所有可選的方法。迭代器提供的iterator()方法不保證遍歷優(yōu)先級(jí)隊(duì)列的元素根據(jù)任何特別的順序。如果你需要有序的遍歷，考慮使用Arrays.sort(pq.toArray()).
注意，PriorityQueue類的實(shí)現(xiàn)是非同步的。如果任何一個(gè)線程修改隊(duì)列，多線程不應(yīng)該同時(shí)訪問(wèn)一個(gè)PriorityQueue實(shí)例。相反，應(yīng)該使用線程安全的PriorityBlockingQueue類。
實(shí)現(xiàn)注意：該實(shí)現(xiàn)提供了O(log(n))時(shí)間復(fù)雜度對(duì)于入隊(duì)和出隊(duì)方法：offer、poll、remove()和add；線性的時(shí)間O(n)對(duì)于remove(object)和contains(object)方法；和常量的時(shí)間O(1)對(duì)于檢索方法：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)先級(jí)隊(duì)列表現(xiàn)為一個(gè)平衡二項(xiàng)堆(即，平衡二叉樹)：queue[n]的兩個(gè)兒子分別是queue[2n+1]和queue[2(n+1)]。優(yōu)先級(jí)隊(duì)列通過(guò)比較器(comparator)來(lái)排序，或者如果比較器為空則通過(guò)元素的自然順序來(lái)排序：堆中每個(gè)節(jié)點(diǎn)n和n的每個(gè)后裔節(jié)點(diǎn)d，n <= d。假設(shè)隊(duì)列是非空的，那么具有最低值的元素在queue[0]。
優(yōu)先級(jí)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)是一個(gè)平衡二叉樹，并且數(shù)中所有的子節(jié)點(diǎn)必須大于等于父節(jié)點(diǎn)，而同一層子節(jié)點(diǎn)間無(wú)需維護(hù)大小關(guān)系。這樣的結(jié)構(gòu)性讓優(yōu)先級(jí)隊(duì)列看起來(lái)像是一個(gè)最小堆。
① 假設(shè)父節(jié)點(diǎn)為queue[n]，那么左孩子節(jié)點(diǎn)為queue[2n+1]，右孩子節(jié)點(diǎn)為queue[2(n+1)]。
② 假設(shè)孩子節(jié)點(diǎn)(無(wú)論是左孩子節(jié)點(diǎn)還是右孩子節(jié)點(diǎn))為queue[n]，n>0。那么父節(jié)點(diǎn)為queue[(n-1) >>> 1]
節(jié)點(diǎn)間的大小關(guān)系：
① 父節(jié)點(diǎn)總是小于等于孩子節(jié)點(diǎn)
② 同一層孩子節(jié)點(diǎn)間的大小無(wú)需維護(hù)
葉子節(jié)點(diǎn)與非葉子節(jié)點(diǎn)：
① 一個(gè)長(zhǎng)度為size的優(yōu)先級(jí)隊(duì)列，當(dāng)index >= size >>> 1時(shí)，該節(jié)點(diǎn)為葉子節(jié)點(diǎn)。否則，為非葉子節(jié)點(diǎn)。"附"中會(huì)對(duì)該結(jié)論做個(gè)簡(jiǎn)單的證明。
/**
* 優(yōu)先級(jí)隊(duì)列元素的個(gè)數(shù)
*/
private int size = 0;
/**
* 優(yōu)先級(jí)隊(duì)列結(jié)構(gòu)上被修改的次數(shù)。修改操作包括：clear()、offer(E)、poll()、removeAt(int)
*/
transient int modCount = 0; // non-private to simplify nested class access
方法
- 添加節(jié)點(diǎn)
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)先級(jí)隊(duì)列中插入元素，如果隊(duì)列滿了，則進(jìn)行擴(kuò)容。插入操作必要的話是會(huì)導(dǎo)致堆元素調(diào)整的，以滿足父節(jié)點(diǎn)總是小于等于子節(jié)點(diǎn)的要求。
插入操作的時(shí)間復(fù)雜度為O(log(n));
通過(guò)siftUp方法來(lái)完成元素插入時(shí)的調(diào)整：siftUp(index, object)方法會(huì)升高待插入元素在樹中的位置index，直到待插入的元素大于或等于它待插入位置的父節(jié)點(diǎn)
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;
}
通過(guò)“int parent = (k - 1) >>> 1;”獲取到當(dāng)前要插入節(jié)點(diǎn)位置的父節(jié)點(diǎn)，比較父節(jié)點(diǎn)和待插入節(jié)點(diǎn)，如果待插入節(jié)點(diǎn)小于父節(jié)點(diǎn)，則將父節(jié)點(diǎn)插入到子節(jié)點(diǎn)的位置，然后在獲取父節(jié)點(diǎn)的父節(jié)點(diǎn)循環(huán)上面的操作，直到待插入節(jié)點(diǎn)大于等于父節(jié)點(diǎn)，則在相應(yīng)位置插入這個(gè)節(jié)點(diǎn)。最終保證代表優(yōu)先級(jí)隊(duì)列的平衡二叉樹中，所有的子節(jié)點(diǎn)都大于它們的父節(jié)點(diǎn)，但同一層的子節(jié)點(diǎn)間并不需要維護(hù)大小關(guān)系。
圖解“添加節(jié)點(diǎn)”步驟：
往一個(gè)空的優(yōu)先級(jí)隊(duì)列中依次插入“13”、“-3”、“20”、“-25”
① 插入“13”
② 插入“-3”
③ 插入“20”
④ 插入“-25”
- 獲取優(yōu)先級(jí)隊(duì)列頭結(jié)點(diǎn)
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
獲取優(yōu)先級(jí)隊(duì)列頭元素，也就是優(yōu)先級(jí)隊(duì)列中值最小的元素。
獲取操作的時(shí)間復(fù)雜度為O(1)
- 刪除節(jié)點(diǎn)
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
該刪除操作的最壞耗時(shí)為：n + 2log(n); 所以該操作的的時(shí)間復(fù)雜度為O(n);
indexOf(object)操作時(shí)間復(fù)雜度為O(n);
removeAt(index)操作時(shí)間復(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é)點(diǎn)位置為隊(duì)列尾，則直接將隊(duì)列尾位置置null。否則將隊(duì)列尾節(jié)點(diǎn)前插以覆蓋待刪除節(jié)點(diǎn)位置的節(jié)點(diǎn)。
當(dāng)待刪除節(jié)點(diǎn)的位置為非葉子節(jié)點(diǎn)時(shí)，會(huì)進(jìn)行一系列的節(jié)點(diǎn)調(diào)整，使得隊(duì)尾節(jié)點(diǎn)在前插后能保證優(yōu)先級(jí)隊(duì)列數(shù)據(jù)結(jié)構(gòu)的正確性。
當(dāng)待刪除節(jié)點(diǎn)的位置為葉子節(jié)點(diǎn)時(shí)，會(huì)先將隊(duì)尾節(jié)點(diǎn)設(shè)置到待刪除節(jié)點(diǎn)位置以使得隊(duì)列中已經(jīng)沒(méi)有待刪除節(jié)點(diǎn)了，然后再進(jìn)行已經(jīng)插入到新位置的隊(duì)尾節(jié)點(diǎn)同它新父節(jié)點(diǎn)進(jìn)行比較調(diào)整，以保證父節(jié)點(diǎn)總是小于等于子節(jié)點(diǎn)，即保證優(yōu)先級(jí)隊(duì)列數(shù)據(jù)結(jié)構(gòu)的正確性。
當(dāng)該方法進(jìn)行siftUp操作來(lái)對(duì)節(jié)點(diǎn)進(jìn)行結(jié)構(gòu)調(diào)整后使得隊(duì)尾節(jié)點(diǎn)最終并不是被設(shè)置到了待刪除節(jié)點(diǎn)位置，這時(shí)就返回這個(gè)前插的隊(duì)尾元素。因?yàn)檫@種情況下，刪除操作會(huì)涉及到一個(gè)未訪問(wèn)的元素被移動(dòng)到了一個(gè)已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)位置。在迭代器操作中需要特殊處理。
通過(guò)siftDown方法來(lái)完成元素移除時(shí)的調(diào)整：siftDown(index, object)方法會(huì)降低待插入元素在樹中的位置index，直到待插入的元素小于或等于它待插入位置的孩子節(jié)點(diǎn)。
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;
}
因?yàn)樵谄胶舛鏄渲?，葉子節(jié)點(diǎn)的個(gè)數(shù)總是大于等于前面所有非葉子節(jié)點(diǎn)個(gè)數(shù)之和。所有如果待刪除元素的所在位置大于等于隊(duì)列長(zhǎng)度的一半，則說(shuō)明待刪除的節(jié)點(diǎn)是一個(gè)葉子節(jié)點(diǎn)，則直接將隊(duì)列中最后一個(gè)節(jié)點(diǎn)值(注意，隊(duì)列中最后一個(gè)節(jié)點(diǎn)一定也是葉子節(jié)點(diǎn))設(shè)置到待刪除節(jié)點(diǎn)所在位置。
如果待刪除節(jié)點(diǎn)的位置小于隊(duì)列長(zhǎng)度的一半，則說(shuō)明待刪除的節(jié)點(diǎn)是一個(gè)非葉子節(jié)點(diǎn)。那么先取得待刪除節(jié)點(diǎn)的子節(jié)點(diǎn)中小的那個(gè)子節(jié)點(diǎn)，將該子節(jié)點(diǎn)與隊(duì)列中最后一個(gè)節(jié)點(diǎn)進(jìn)行比較，如果子節(jié)點(diǎn)小于隊(duì)列中最后一個(gè)節(jié)點(diǎn)，則將子節(jié)點(diǎn)值設(shè)置到待刪除節(jié)點(diǎn)的位置，然后再次獲取當(dāng)前子節(jié)點(diǎn)的較小的子節(jié)點(diǎn)重復(fù)一樣的操作，直到隊(duì)列最后一個(gè)節(jié)點(diǎn)比較小的那個(gè)子節(jié)點(diǎn)還要小，則將隊(duì)列最后一個(gè)節(jié)點(diǎn)值設(shè)置為這個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)。最終保證代表優(yōu)先級(jí)隊(duì)列的平衡二叉樹中，所有的父節(jié)點(diǎn)都小于等于它的子節(jié)點(diǎn)，但同一層的子節(jié)點(diǎn)間并不需要維護(hù)大小關(guān)系。
圖解“刪除節(jié)點(diǎn)”步驟：
假設(shè)有如下優(yōu)先級(jí)隊(duì)列：
情況二：刪除“queue[2]=-23”
- 是否包含節(jié)點(diǎn)
public boolean contains(Object o) {
return indexOf(o) != -1;
}
判斷優(yōu)先級(jí)隊(duì)列中是否包含object對(duì)象。該方法的時(shí)間復(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)先級(jí)隊(duì)列頭節(jié)點(diǎn)
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)先級(jí)隊(duì)列頭節(jié)點(diǎn)。該操作的時(shí)間復(fù)雜度為：O(log(n));
- 清除優(yōu)先級(jí)隊(duì)列中所有節(jié)點(diǎn)
modCount++;
for (int i = 0; i < size; i++)
queue[i] = null;
size = 0;
}
清除優(yōu)先級(jí)隊(duì)列中的所有節(jié)點(diǎn)。該操作的事件復(fù)雜度為：O(n);
- 迭代器
優(yōu)先級(jí)隊(duì)列的迭代器并不保證遍歷按照指定的順序獲取節(jié)點(diǎn)元素。這是因?yàn)楫?dāng)在迭代器中執(zhí)行remove操作時(shí)，可能會(huì)涉及到一個(gè)未訪問(wèn)的元素被移動(dòng)到了一個(gè)已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)位置(刪除操作時(shí)，當(dāng)隊(duì)尾節(jié)點(diǎn)被放置到待移除節(jié)點(diǎn)位置的情況下，需要調(diào)用siftUp方法，siftUp(index, object)方法會(huì)升高待插入元素在樹中的位置index，直到待插入的元素大于或等于它待插入位置的父節(jié)點(diǎn))。在迭代器操作中需要特殊處理。此時(shí)這些不幸的元素會(huì)在所有節(jié)點(diǎn)遍歷完后才得以遍歷。
附
- 證明“在平衡二叉樹中，葉子節(jié)點(diǎn)的個(gè)數(shù)總是大于等于前面所有非葉子節(jié)點(diǎn)個(gè)數(shù)之和?！?br>
一個(gè)平衡二叉樹第N層節(jié)點(diǎn)數(shù)為：2^N
一個(gè)N層的平衡二叉樹總節(jié)點(diǎn)數(shù)為：2^(N+1) -1；
Sn = 2^0 + 2^1 + …… + 2^N
2*Sn = 2^1 + 2^2 + …… + 2^N + 2^(N+1)
將二個(gè)等式的左邊和右邊分別進(jìn)行相減操作得到：
(2-1)Sn = 2^(N+1) - 2^0 ==> Sn = 2^(N+1) -1;
所以一個(gè)N層的二叉平衡樹除了葉子節(jié)點(diǎn)外的節(jié)點(diǎn)總數(shù)最大為：2^N -1；
因而2^N > 2^N -1，所以在滿平衡二叉樹下，葉子節(jié)點(diǎn)大于非葉子節(jié)點(diǎn)個(gè)數(shù)之和，當(dāng)然在最后一層節(jié)點(diǎn)不滿的情況下，葉子節(jié)點(diǎn)依舊大于等于所有非葉子之和。
后記
若文章有任何錯(cuò)誤，望大家不吝指教:)
