深入淺析JDK中的PriorityQueue？針對這個問題，這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
專注于為中小企業(yè)提供網(wǎng)站設(shè)計制作、做網(wǎng)站服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)武進(jìn)免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
一.優(yōu)先隊列的應(yīng)用
優(yōu)先隊列在程序開發(fā)中屢見不鮮，比如操作系統(tǒng)在進(jìn)行進(jìn)程調(diào)度時一種可行的算法是使用優(yōu)先隊列，當(dāng)一個新的進(jìn)程被fork()出來后，首先將它放到隊列的最后，而操作系統(tǒng)內(nèi)部的Scheduler負(fù)責(zé)不斷地從這個優(yōu)先隊列中取出優(yōu)先級較高的進(jìn)程執(zhí)行；爬蟲系統(tǒng)在執(zhí)行時往往也需要從一個優(yōu)先級隊列中循環(huán)取出高優(yōu)先級任務(wù)并進(jìn)行抓取?？梢韵胍?，如果類似這樣的任務(wù)不適用優(yōu)先級進(jìn)行劃分的話，系統(tǒng)必會出現(xiàn)故障，例如操作系統(tǒng)中低優(yōu)先級進(jìn)程持續(xù)占用資源而高優(yōu)先級進(jìn)程始終在隊列中等待。此外，優(yōu)先隊列在貪婪算法中也有一些應(yīng)用。
二.優(yōu)先隊列的實現(xiàn)原理
優(yōu)先隊列的實現(xiàn)方式是使用二叉堆的結(jié)構(gòu)，需要滿足以下兩條性質(zhì)(Heap property)，這里以小頂堆為例講解：
1.任何結(jié)點的值都小于或等于其子節(jié)點的值。
2.所有結(jié)點從上到下，從左到右填入，即一棵完全二叉樹。
基于這兩條規(guī)律，二叉堆在實現(xiàn)中往往會使用一個數(shù)組，下面我們研究一下JDK中二叉堆(優(yōu)先隊列)的實現(xiàn)。
三.優(yōu)先隊列在JDK中的實現(xiàn)方式
研究源碼最好的方式是debug，看每一步變量的變化，我們可以簡單寫一個Demo，debug進(jìn)源碼一探究竟：
這里我們簡單地創(chuàng)建一個優(yōu)先隊列，向其中添加三個元素，我們可以在代碼第一行打一個斷點，如果您使用Eclipse編輯器的話，接下來可以按F5進(jìn)入源碼中：
代碼運行到這里，PriorityQueue調(diào)用自己的一個重載構(gòu)造器，第一個參數(shù)是數(shù)組默認(rèn)大小，第二個是元素比較的Comparator,我們這里的Demo比較簡單，您在使用優(yōu)先隊列時可以選擇實現(xiàn)自己的Comparator。
重慶分公司
重慶分公司
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}接下來我們研究一下添加元素時的offer操作：
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
//記錄了隊列被修改的次數(shù)
modCount++;
int i = size;
if (i >= queue.length)
//擴(kuò)容
grow(i + 1);
//增加元素個數(shù)
size = i + 1;
if (i == 0)
//第一次添加元素，直接放到第0個位置即可
queue[0] = e;
else
//需要將元素放到最后，再做上濾操作
siftUp(i, e);
return true;
}我們逐行來解釋一下，首先offer方法判斷參數(shù)是否為空，不為空則對變量modCount自增，modCount記錄了隊列被修改的次數(shù)，接下來，判斷數(shù)組是否會越界，如果越界則通過grow進(jìn)行擴(kuò)容，接下來添加元素，如果當(dāng)前元素為0個則直接將元素放到數(shù)組第一個位置，否則做一個siftUp的操作。
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//元素拷貝
queue = Arrays.copyOf(queue, newCapacity);上面的代碼對隊列擴(kuò)容，源碼中注釋也很清晰，首先判斷當(dāng)前的數(shù)組大小是否足夠小(<64)，如果足夠小則將大小擴(kuò)充為2倍，否則將原大小加上50%。需要注意的是，這里最后做了一個大小是否溢出的判斷。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}如果需要擴(kuò)容的大小已經(jīng)<0了，顯然已經(jīng)溢出了，在這里拋出了OutOfMemory的異常。
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
//計算父親節(jié)點的下標(biāo)
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//與父節(jié)點進(jìn)行比較
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}為了保證優(yōu)先隊列的性質(zhì)1，在插入每個元素時都需要與該節(jié)點父親進(jìn)行比較，找到其正確位置，有些數(shù)據(jù)結(jié)構(gòu)書中，這個操作被稱為上濾(percolate up)。
入隊操作已經(jīng)說完了，接下來是出隊操作，即poll()操作：
public E poll() {
if (size == 0)
return null;
int s = --size;
//自增變量，代表隊列修改次數(shù)
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}這個方法首先將數(shù)組第一個元素作為結(jié)果，(因為如果是小頂堆的話堆頂始終是最小元素)，并將隊列的最后一個元素放到第一個位置，最后用siftDown做一些調(diào)整，保證隊列的性質(zhì)，這個操作被稱為下濾(percolate down)。
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
//這里k必須有孩子，故葉節(jié)點需要比較
while (k < half) {
//以下幾行代碼到較小的那個兒子,用變量c表示
int child = (k << 1) + 1;
//這里假設(shè)左兒子比較小
Object c = queue[child];
int right = child + 1;
//左右兒子比較，如果右兒子小則將c賦值為右兒子
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
//如果x比小兒子還小，說明k就是正確位置
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}下濾過程中k不斷與其兒子進(jìn)行比較，如果滿足優(yōu)先隊列的順序性，則break出循環(huán)。
關(guān)于深入淺析JDK中的PriorityQueue問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識。
