上一篇我們知道了PriorityDeque的底層結(jié)構(gòu)，是個(gè)平衡二叉堆，用“兵陣變隊(duì)列”的方式儲(chǔ)存在數(shù)組中。
這一篇我們開始學(xué)習(xí)，PriorityDeque是如何利用平衡二叉堆實(shí)現(xiàn)優(yōu)先級(jí)排序的。
先看添加元素的方法：
public boolean add(E e) {
return offer(e);
}
原來(lái)add是offer封裝而已，看看offer源碼：
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
siftUp(i, e);
size = i + 1;
return true;
}
offer添加元素的邏輯如下：
- modCount操作次數(shù)加1，默認(rèn)是0
- size是隊(duì)列長(zhǎng)度，默認(rèn)是0
- 如果數(shù)組長(zhǎng)度不夠，則需要調(diào)用
grow擴(kuò)容 - 數(shù)組長(zhǎng)度足夠，調(diào)用
siftUp進(jìn)行元素添加 - 隊(duì)列長(zhǎng)度size加1
grow函數(shù)我們比較熟悉了，基本上java里面的自動(dòng)數(shù)組擴(kuò)容都是這個(gè)邏輯：長(zhǎng)度在64以下是擴(kuò)容至原長(zhǎng)度2倍+2；大于64長(zhǎng)度就是每次擴(kuò)容50%。當(dāng)然會(huì)充分考慮一些越界問題。
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
/* preferred growth */);
queue = Arrays.copyOf(queue, newCapacity);
}
接下來(lái)，我們重點(diǎn)看之前沒見過(guò)的函數(shù)siftUp(int k, E x)：
/**
* Inserts item x at position k, maintaining heap invariant by
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
* To simplify and speed up coercions and comparisons, the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
* @param k the position to fill
* @param x the item to insert
*/
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x, queue, comparator);
else
siftUpComparable(k, x, queue);
}
siftUp的邏輯如下：
- 如果我們構(gòu)造函數(shù)時(shí)候傳入了自定義的
comparator比較器，就用siftUpUsingComparator進(jìn)行優(yōu)先級(jí)判斷加入； - 如果沒有自定義比較器，就用默認(rèn)的
siftUpComparable函數(shù)進(jìn)行排序后再加入。
注釋提到，siftUp實(shí)現(xiàn)在數(shù)組的k位置插入元素x，通過(guò)“上浮”x直到它大于或等于其父節(jié)點(diǎn)，或者x變成根節(jié)點(diǎn)，來(lái)保持最小堆的平衡，就是“小頂堆”。為了簡(jiǎn)化和加速比較，默認(rèn)比較器和自定義比較器被分成不同的方法，其他實(shí)現(xiàn)是相同的。(類似siftDown。)
那么，既然注釋siftUpComparable和siftUpUsingComparator就差個(gè)自定義比較而已，那么我們先看默認(rèn)的排序函數(shù)siftUpComparable的實(shí)現(xiàn)邏輯：
/**
* 將元素x插到數(shù)組k的位置.
* 然后按照元素的自然順序進(jìn)行堆調(diào)整——"上浮"，以維持"堆"有序.
* 最終的結(jié)果是一個(gè)"小頂堆".
*/
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
// 這個(gè)k就是我們傳進(jìn)來(lái)的隊(duì)列長(zhǎng)度，默認(rèn)是0
while (k > 0) {
// (k-1)除2, 求出k結(jié)點(diǎn)的父結(jié)點(diǎn)索引parent
// 例如，k等于1或者2，那么k的父節(jié)點(diǎn)在數(shù)組位置0
// 如果，k等于3，那么k的父節(jié)點(diǎn)在數(shù)組位置1
int parent = (k - 1) >>> 1;
// 取出父節(jié)點(diǎn)的元素
Object e = es[parent];
// 如果插入的元素值大于等于父結(jié)點(diǎn)元素值, 則退出“上浮”循環(huán)
if (key.compareTo((T) e) >= 0)
break;
// 如果插入的元素值小于父結(jié)點(diǎn)元素值, 則把父節(jié)點(diǎn)放到k的位置
es[k] = e;
// 繼續(xù)向上找下一個(gè)父節(jié)點(diǎn)是否需要上浮調(diào)整
k = parent;
}
// 上浮調(diào)整結(jié)束，找到適合元素key的位置k，保存到數(shù)組中
es[k] = key;
}
原來(lái)，siftUpComparable方法的作用其實(shí)就是堆的“上浮調(diào)整”，可以把平衡二叉堆想象成一棵完全二叉樹，每次插入元素都鏈接到二叉樹的最右下方，然后將插入的元素與其父結(jié)點(diǎn)比較，如果父結(jié)點(diǎn)大，則交換元素，直到?jīng)]有父結(jié)點(diǎn)比插入的結(jié)點(diǎn)大為止。這樣就保證了堆頂（二叉樹的根結(jié)點(diǎn)）一定是最小的元素。（注：以上僅針對(duì)“小頂堆”）
再看看siftUpUsingComparator，只是if那句換成if (key.compareTo((T) e) >= 0)而已，所以就不再重復(fù)闡述了。
如果換成自定義的優(yōu)先級(jí)比較器?？梢韵胂筱y行的各種金卡黑卡普通卡排隊(duì)比較。只要金卡來(lái)了，就會(huì)排比黑卡、普通卡排前面。黑卡來(lái)了也可以插普通卡的隊(duì)。
“有錢大曬?。俊?br> “抱歉，有錢是真的能為所欲為的?！?/p>
這種操作就是折半法查找，每找一次排除一半的可能，256個(gè)數(shù)據(jù)中查找只要找8次就可以找到目標(biāo)，2^x =N，所以時(shí)間復(fù)雜度x=Ο(logN)。
ok，總結(jié)下今天的結(jié)論：
- PriorityQueue的默認(rèn)優(yōu)先級(jí)是數(shù)值從小到大排序
- 排序比較的過(guò)程就是堆的上浮處理過(guò)程，可以想象銀行金卡、黑卡各種插隊(duì)普通卡
- 上浮算法的關(guān)鍵是通過(guò) (k - 1) / 2 找到k的父節(jié)點(diǎn)，再根據(jù)優(yōu)先級(jí)是否調(diào)換位置
- 時(shí)間復(fù)雜度是Ο(logN)
