一、PriorityQueue的數(shù)據(jù)結(jié)構(gòu)
JDK7中PriorityQueue（優(yōu)先級(jí)隊(duì)列）的數(shù)據(jù)結(jié)構(gòu)是二叉堆。準(zhǔn)確的說(shuō)是一個(gè)最小堆。
二叉堆是一個(gè)特殊的堆， 它近似完全二叉樹。二叉堆滿足特性：父節(jié)點(diǎn)的鍵值總是保持固定的序關(guān)系于任何一個(gè)子節(jié)點(diǎn)的鍵值，且每個(gè)節(jié)點(diǎn)的左子樹和右子樹都是一個(gè)二叉堆。
當(dāng)父節(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。 當(dāng)父節(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。
下圖是一個(gè)最大堆
priorityQueue隊(duì)頭就是給定順序的最小元素。
priorityQueue不允許空值且不支持non-comparable的對(duì)象。priorityQueue要求使用Comparable和Comparator接口給對(duì)象排序，并且在排序時(shí)會(huì)按照優(yōu)先級(jí)處理其中的元素。
priorityQueue的大小是無(wú)限制的（unbounded）, 但在創(chuàng)建時(shí)可以指定初始大小。當(dāng)增加隊(duì)列元素時(shí)，隊(duì)列會(huì)自動(dòng)擴(kuò)容。
priorityQueue不是線程安全的， 類似的PriorityBlockingQueue是線程安全的。
我們知道隊(duì)列是遵循先進(jìn)先出（First-In-First-Out）模式的，但有些時(shí)候需要在隊(duì)列中基于優(yōu)先級(jí)處理對(duì)象。舉個(gè)例子，比方說(shuō)我們有一個(gè)每日交易時(shí)段生成股票報(bào)告的應(yīng)用程序，需要處理大量數(shù)據(jù)并且花費(fèi)很多處理時(shí)間。客戶向這個(gè)應(yīng)用程序發(fā)送請(qǐng)求時(shí)，實(shí)際上就進(jìn)入了隊(duì)列。我們需要首先處理優(yōu)先客戶再處理普通用戶。在這種情況下，Java的PriorityQueue(優(yōu)先隊(duì)列)會(huì)很有幫助。
PriorityQueue是基于優(yōu)先堆的一個(gè)無(wú)界隊(duì)列，這個(gè)優(yōu)先隊(duì)列中的元素可以默認(rèn)自然排序或者通過(guò)提供的Comparator（比較器）在隊(duì)列實(shí)例化的時(shí)排序。
優(yōu)先隊(duì)列不允許空值，而且不支持non-comparable（不可比較）的對(duì)象，比如用戶自定義的類。優(yōu)先隊(duì)列要求使用Java Comparable和Comparator接口給對(duì)象排序，并且在排序時(shí)會(huì)按照優(yōu)先級(jí)處理其中的元素。
優(yōu)先隊(duì)列的頭是基于自然排序或者Comparator排序的最小元素。如果有多個(gè)對(duì)象擁有同樣的排序，那么就可能隨機(jī)地取其中任意一個(gè)。當(dāng)我們獲取隊(duì)列時(shí)，返回隊(duì)列的頭對(duì)象。
優(yōu)先隊(duì)列的大小是不受限制的，但在創(chuàng)建時(shí)可以指定初始大小。當(dāng)我們向優(yōu)先隊(duì)列增加元素的時(shí)候，隊(duì)列大小會(huì)自動(dòng)增加。
PriorityQueue是非線程安全的，所以Java提供了PriorityBlockingQueue（實(shí)現(xiàn)BlockingQueue接口）用于Java多線程環(huán)境。
二、PriorityQueue源碼分析
成員：
|
1
2
|
priavte transient Object[] queue;private int size = 0; |
1.PriorityQueue構(gòu)造小頂堆的過(guò)程
這里我們以priorityQueue構(gòu)造器傳入一個(gè)容器為參數(shù)PriorityQueue(Collecntion<? extends E>的例子：
構(gòu)造小頂堆的過(guò)程大體分兩步：
復(fù)制容器數(shù)據(jù)，檢查容器數(shù)據(jù)是否為null
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
private void initElementsFromCollection(Collection<? extends E> c) { Object[] a = c.toArray(); // If c.toArray incorrectly doesn't return Object[], copy it. if (a.getClass() != Object[].class) a = Arrays.copyOf(a, a.length, Object[].class); int len = a.length; if (len == 1 || this.comparator != null) for (int i = 0; i < len; i++) if (a[i] == null) throw new NullPointerException(); this.queue = a; this.size = a.length;} |
調(diào)整，使數(shù)據(jù)滿足小頂堆的結(jié)構(gòu)。
首先介紹兩個(gè)調(diào)整方式siftUp和siftDown
siftDown: 在給定初始化元素的時(shí)候，要調(diào)整元素，使其滿足最小堆的結(jié)構(gòu)性質(zhì)。因此不停地從上到下將元素x的鍵值與孩子比較并做交換，直到找到元素x的鍵值小于等于孩子的鍵值（即保證它比其左右結(jié)點(diǎn)值小），或者是下降到葉子節(jié)點(diǎn)為止。
例如如下的示意圖，調(diào)整9這個(gè)節(jié)點(diǎn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // size/2是第一個(gè)葉子結(jié)點(diǎn)的下標(biāo) //只要沒(méi)到葉子節(jié)點(diǎn) while (k < half) { int child = (k << 1) + 1; // 左孩子 Object c = queue[child]; int right = child + 1; //找出左右孩子中小的那個(gè) 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;} |
siftUp: priorityQueue每次新增加一個(gè)元素的時(shí)候是將新元素插入對(duì)尾的。因此，應(yīng)該與siftDown有同樣的調(diào)整過(guò)程，只不過(guò)是從下（葉子）往上調(diào)整。
例如如下的示意圖，填加key為3的節(jié)點(diǎn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; //獲取parent下標(biāo) Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key;} |
總體的建立小頂堆的過(guò)程就是：
|
1
2
3
4
|
private void initFromCollection(Collection<? extends E> c) { initElementsFromCollection(c); heapify(); } |
其中heapify就是siftDown的過(guò)程。
2.PriorityQueue容量擴(kuò)容過(guò)程
從實(shí)例成員可以看出，PriorityQueue維護(hù)了一個(gè)Object[], 因此它的擴(kuò)容方式跟順序表ArrayList相差不多。
這里只給出grow方法的源碼
|
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); } |
可以看出，當(dāng)數(shù)組的Capacity不大的時(shí)候，每次擴(kuò)容也不大。當(dāng)數(shù)組容量大于64的時(shí)候，每次擴(kuò)容double。
三、PriorityQueue的應(yīng)用
eg1：
這里給出一個(gè)最簡(jiǎn)單的應(yīng)用：從動(dòng)態(tài)數(shù)據(jù)中求第K個(gè)大的數(shù)。
思路就是維持一個(gè)size = k 的小頂堆。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//data是動(dòng)態(tài)數(shù)據(jù)//heap維持動(dòng)態(tài)數(shù)據(jù)的堆//res用來(lái)保存第K大的值public boolean kthLargest(int data, int k, PriorityQueue<Integer> heap, int[] res) { if(heap.size() < k) { heap.offer(data); if(heap.size() == k) { res[0] = heap.peek(); return true; } return false; } if(heap.peek() < data) { heap.poll(); heap.offer(data); } res[0] = heap.peek(); return true;} |
eg2：
我們有一個(gè)用戶類Customer，它沒(méi)有提供任何類型的排序。當(dāng)我們用它建立優(yōu)先隊(duì)列時(shí)，應(yīng)該為其提供一個(gè)比較器對(duì)象。
Customer.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
package com.journaldev.collections; public class Customer { private int id; private String name; public Customer(int i, String n){ this.id=i; this.name=n; } public int getId() { return id; } public String getName() { return name; } } |
我們使用Java隨機(jī)數(shù)生成隨機(jī)用戶對(duì)象。對(duì)于自然排序，我們使用Integer對(duì)象，這也是一個(gè)封裝過(guò)的Java對(duì)象。
下面是最終的測(cè)試代碼，展示如何使用PriorityQueue：
PriorityQueueExample.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
package com.journaldev.collections; import java.util.Comparator;import java.util.PriorityQueue;import java.util.Queue;import java.util.Random; public class PriorityQueueExample { public static void main(String[] args) { //優(yōu)先隊(duì)列自然排序示例 Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7); Random rand = new Random(); for(int i=0;i<7;i++){ integerPriorityQueue.add(new Integer(rand.nextInt(100))); } for(int i=0;i<7;i++){ Integer in = integerPriorityQueue.poll(); System.out.println("Processing Integer:"+in); } //優(yōu)先隊(duì)列使用示例 Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator); addDataToQueue(customerPriorityQueue); pollDataFromQueue(customerPriorityQueue); } //匿名Comparator實(shí)現(xiàn) public static Comparator<Customer> idComparator = new Comparator<Customer>(){ @Override public int compare(Customer c1, Customer c2) { return (int) (c1.getId() - c2.getId()); } }; //用于往隊(duì)列增加數(shù)據(jù)的通用方法 private static void addDataToQueue(Queue<Customer> customerPriorityQueue) { Random rand = new Random(); for(int i=0; i<7; i++){ int id = rand.nextInt(100); customerPriorityQueue.add(new Customer(id, "Pankaj "+id)); } } //用于從隊(duì)列取數(shù)據(jù)的通用方法 private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) { while(true){ Customer cust = customerPriorityQueue.poll(); if(cust == null) break; System.out.println("Processing Customer with ID="+cust.getId()); } } } |
注意我用實(shí)現(xiàn)了Comparator接口的Java匿名類，并且實(shí)現(xiàn)了基于id的比較器。
當(dāng)我運(yùn)行以上測(cè)試程序時(shí)，我得到以下輸出：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
Processing Integer:9Processing Integer:16Processing Integer:18Processing Integer:25Processing Integer:33Processing Integer:75Processing Integer:77Processing Customer with ID=6Processing Customer with ID=20Processing Customer with ID=24Processing Customer with ID=28Processing Customer with ID=29Processing Customer with ID=82Processing Customer with ID=96 |
從輸出結(jié)果可以清楚的看到，最小的元素在隊(duì)列的頭部因而最先被取出。如果不實(shí)現(xiàn)Comparator，在建立customerPriorityQueue時(shí)會(huì)拋出ClassCastException。
|
1
2
3
4
5
6
7
|
Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633) at java.util.PriorityQueue.siftUp(PriorityQueue.java:629) at java.util.PriorityQueue.offer(PriorityQueue.java:329) at java.util.PriorityQueue.add(PriorityQueue.java:306) at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45) at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25) |
