一.優(yōu)先隊(duì)列的應(yīng)用
優(yōu)先隊(duì)列在程序開(kāi)發(fā)中屢見(jiàn)不鮮，比如操作系統(tǒng)在進(jìn)行進(jìn)程調(diào)度時(shí)一種可行的算法是使用優(yōu)先隊(duì)列，當(dāng)一個(gè)新的進(jìn)程被fork()出來(lái)后，首先將它放到隊(duì)列的最后，而操作系統(tǒng)內(nèi)部的Scheduler負(fù)責(zé)不斷地從這個(gè)優(yōu)先隊(duì)列中取出優(yōu)先級(jí)較高的進(jìn)程執(zhí)行；爬蟲(chóng)系統(tǒng)在執(zhí)行時(shí)往往也需要從一個(gè)優(yōu)先級(jí)隊(duì)列中循環(huán)取出高優(yōu)先級(jí)任務(wù)并進(jìn)行抓取。可以想見(jiàn)，如果類(lèi)似這樣的任務(wù)不適用優(yōu)先級(jí)進(jìn)行劃分的話，系統(tǒng)必會(huì)出現(xiàn)故障，例如操作系統(tǒng)中低優(yōu)先級(jí)進(jìn)程持續(xù)占用資源而高優(yōu)先級(jí)進(jìn)程始終在隊(duì)列中等待。此外，優(yōu)先隊(duì)列在貪婪算法中也有一些應(yīng)用。
二.優(yōu)先隊(duì)列的實(shí)現(xiàn)原理
優(yōu)先隊(duì)列的實(shí)現(xiàn)方式是使用二叉堆的結(jié)構(gòu)，需要滿足以下兩條性質(zhì)(Heap property)，這里以小頂堆為例講解：
1.任何結(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。
2.所有結(jié)點(diǎn)從上到下，從左到右填入，即一棵完全二叉樹(shù)。
基于這兩條規(guī)律，二叉堆在實(shí)現(xiàn)中往往會(huì)使用一個(gè)數(shù)組，下面我們研究一下JDK中二叉堆(優(yōu)先隊(duì)列)的實(shí)現(xiàn)。
三.優(yōu)先隊(duì)列在JDK中的實(shí)現(xiàn)方式
研究源碼最好的方式是debug，看每一步變量的變化，我們可以簡(jiǎn)單寫(xiě)一個(gè)Demo，debug進(jìn)源碼一探究竟：
這里我們簡(jiǎn)單地創(chuàng)建一個(gè)優(yōu)先隊(duì)列，向其中添加三個(gè)元素，我們可以在代碼第一行打一個(gè)斷點(diǎn)，如果您使用Eclipse編輯器的話，接下來(lái)可以按F5進(jìn)入源碼中：
代碼運(yùn)行到這里，PriorityQueue調(diào)用自己的一個(gè)重載構(gòu)造器，第一個(gè)參數(shù)是數(shù)組默認(rèn)大小，第二個(gè)是元素比較的Comparator,我們這里的Demo比較簡(jiǎn)單，您在使用優(yōu)先隊(duì)列時(shí)可以選擇實(shí)現(xiàn)自己的Comparator。
|
1
2
3
4
5
6
7
8
9
|
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; } |
接下來(lái)我們研究一下添加元素時(shí)的offer操作：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public boolean offer(E e) { if (e == null) throw new NullPointerException(); //記錄了隊(duì)列被修改的次數(shù) modCount++; int i = size; if (i >= queue.length) //擴(kuò)容 grow(i + 1); //增加元素個(gè)數(shù) size = i + 1; if (i == 0) //第一次添加元素，直接放到第0個(gè)位置即可 queue[0] = e; else //需要將元素放到最后，再做上濾操作 siftUp(i, e); return true; } |
我們逐行來(lái)解釋一下，首先offer方法判斷參數(shù)是否為空，不為空則對(duì)變量modCount自增，modCount記錄了隊(duì)列被修改的次數(shù)，接下來(lái)，判斷數(shù)組是否會(huì)越界，如果越界則通過(guò)grow進(jìn)行擴(kuò)容，接下來(lái)添加元素，如果當(dāng)前元素為0個(gè)則直接將元素放到數(shù)組第一個(gè)位置，否則做一個(gè)siftUp的操作。
|
1
2
3
4
5
6
7
8
9
10
11
|
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); |
上面的代碼對(duì)隊(duì)列擴(kuò)容，源碼中注釋也很清晰，首先判斷當(dāng)前的數(shù)組大小是否足夠小(<64)，如果足夠小則將大小擴(kuò)充為2倍，否則將原大小加上50%。需要注意的是，這里最后做了一個(gè)大小是否溢出的判斷。
|
1
2
3
4
5
6
7
|
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的異常。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
private void siftUpUsingComparator(int k, E x) { while (k > 0) { //計(jì)算父親節(jié)點(diǎn)的下標(biāo) int parent = (k - 1) >>> 1; Object e = queue[parent]; //與父節(jié)點(diǎn)進(jìn)行比較 if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; } |
為了保證優(yōu)先隊(duì)列的性質(zhì)1，在插入每個(gè)元素時(shí)都需要與該節(jié)點(diǎn)父親進(jìn)行比較，找到其正確位置，有些數(shù)據(jù)結(jié)構(gòu)書(shū)中，這個(gè)操作被稱為上濾(percolate up)。
入隊(duì)操作已經(jīng)說(shuō)完了，接下來(lái)是出隊(duì)操作，即poll()操作：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public E poll() { if (size == 0) return null; int s = --size; //自增變量，代表隊(duì)列修改次數(shù) modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s != 0) siftDown(0, x); return result; } |
這個(gè)方法首先將數(shù)組第一個(gè)元素作為結(jié)果，(因?yàn)槿绻切№敹训脑挾秧斒冀K是最小元素)，并將隊(duì)列的最后一個(gè)元素放到第一個(gè)位置，最后用siftDown做一些調(diào)整，保證隊(duì)列的性質(zhì)，這個(gè)操作被稱為下濾(percolate down)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
private void siftDownUsingComparator(int k, E x) { int half = size >>> 1; //這里k必須有孩子，故葉節(jié)點(diǎn)需要比較 while (k < half) { //以下幾行代碼到較小的那個(gè)兒子,用變量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比小兒子還小，說(shuō)明k就是正確位置 if (comparator.compare(x, (E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = x; } |
如上圖，下濾過(guò)程中k不斷與其兒子進(jìn)行比較，如果滿足優(yōu)先隊(duì)列的順序性，則break出循環(huán)。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://www.cnblogs.com/showing/p/6759341.html
