上一篇我們知道了PriorityDeque的底層結(jié)構(gòu)间涵，是個平衡二叉堆任内，用“兵陣變隊列”的方式儲存在數(shù)組中揍很。
這一篇我們開始學習，PriorityDeque是如何利用平衡二叉堆實現(xiàn)優(yōu)先級排序的辆雾。
先看添加元素的方法：
public boolean add(E e) {
return offer(e);
}
原來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，默認是0
- size是隊列長度，默認是0
- 如果數(shù)組長度不夠藤乙，則需要調(diào)用
grow擴容 - 數(shù)組長度足夠猜揪，調(diào)用
siftUp進行元素添加 - 隊列長度size加1
grow函數(shù)我們比較熟悉了，基本上java里面的自動數(shù)組擴容都是這個邏輯：長度在64以下是擴容至原長度2倍+2坛梁；大于64長度就是每次擴容50%湿右。當然會充分考慮一些越界問題。
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);
}
接下來罚勾，我們重點看之前沒見過的函數(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ù)時候傳入了自定義的
comparator比較器毅人，就用siftUpUsingComparator進行優(yōu)先級判斷加入； - 如果沒有自定義比較器尖殃，就用默認的
siftUpComparable函數(shù)進行排序后再加入丈莺。
注釋提到，siftUp實現(xiàn)在數(shù)組的k位置插入元素x送丰，通過“上浮”x直到它大于或等于其父節(jié)點缔俄，或者x變成根節(jié)點，來保持最小堆的平衡器躏，就是“小頂堆”俐载。為了簡化和加速比較，默認比較器和自定義比較器被分成不同的方法登失，其他實現(xiàn)是相同的遏佣。(類似siftDown。)
那么揽浙，既然注釋siftUpComparable和siftUpUsingComparator就差個自定義比較而已状婶，那么我們先看默認的排序函數(shù)siftUpComparable的實現(xiàn)邏輯：
/**
* 將元素x插到數(shù)組k的位置.
* 然后按照元素的自然順序進行堆調(diào)整——"上浮"，以維持"堆"有序.
* 最終的結(jié)果是一個"小頂堆".
*/
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
// 這個k就是我們傳進來的隊列長度馅巷，默認是0
while (k > 0) {
// (k-1)除2, 求出k結(jié)點的父結(jié)點索引parent
// 例如膛虫，k等于1或者2，那么k的父節(jié)點在數(shù)組位置0
// 如果钓猬，k等于3稍刀，那么k的父節(jié)點在數(shù)組位置1
int parent = (k - 1) >>> 1;
// 取出父節(jié)點的元素
Object e = es[parent];
// 如果插入的元素值大于等于父結(jié)點元素值, 則退出“上浮”循環(huán)
if (key.compareTo((T) e) >= 0)
break;
// 如果插入的元素值小于父結(jié)點元素值, 則把父節(jié)點放到k的位置
es[k] = e;
// 繼續(xù)向上找下一個父節(jié)點是否需要上浮調(diào)整
k = parent;
}
// 上浮調(diào)整結(jié)束，找到適合元素key的位置k敞曹，保存到數(shù)組中
es[k] = key;
}
原來账月，siftUpComparable方法的作用其實就是堆的“上浮調(diào)整”，可以把平衡二叉堆想象成一棵完全二叉樹异雁，每次插入元素都鏈接到二叉樹的最右下方捶障，然后將插入的元素與其父結(jié)點比較，如果父結(jié)點大纲刀，則交換元素项炼，直到?jīng)]有父結(jié)點比插入的結(jié)點大為止担平。這樣就保證了堆頂（二叉樹的根結(jié)點）一定是最小的元素。（注：以上僅針對“小頂堆”）
再看看siftUpUsingComparator锭部，只是if那句換成if (key.compareTo((T) e) >= 0)而已暂论，所以就不再重復闡述了。
如果換成自定義的優(yōu)先級比較器拌禾∪√ィ可以想象銀行的各種金卡黑卡普通卡排隊比較。只要金卡來了湃窍，就會排比黑卡闻蛀、普通卡排前面。黑卡來了也可以插普通卡的隊您市。
“有錢大曬熬跬础？”
“抱歉茵休，有錢是真的能為所欲為的薪棒。”
這種操作就是折半法查找俐芯，每找一次排除一半的可能，256個數(shù)據(jù)中查找只要找8次就可以找到目標钉鸯，2^x =N吧史，所以時間復雜度x=Ο(logN)。
ok亏拉，總結(jié)下今天的結(jié)論：
- PriorityQueue的默認優(yōu)先級是數(shù)值從小到大排序
- 排序比較的過程就是堆的上浮處理過程扣蜻，可以想象銀行金卡、黑卡各種插隊普通卡
- 上浮算法的關鍵是通過 (k - 1) / 2 找到k的父節(jié)點及塘，再根據(jù)優(yōu)先級是否調(diào)換位置
- 時間復雜度是Ο(logN)
