解析Java中PriorityQueue優先級隊列構造的源碼及用法。本站提示廣大學習愛好者：（解析Java中PriorityQueue優先級隊列構造的源碼及用法）文章只能為提供參考，不一定能成為您想要的結果。以下是解析Java中PriorityQueue優先級隊列構造的源碼及用法正文
1、PriorityQueue的數據構造
JDK7中PriorityQueue（優先級隊列）的數據構造是二叉堆。精確的說是一個最小堆。
二叉堆是一個特別的堆， 它近似完整二叉樹。二叉堆知足特征：父節點的鍵值老是堅持固定的序關系於任何一個子節點的鍵值，且每一個節點的左子樹和右子樹都是一個二叉堆。
當父節點的鍵值老是年夜於或等於任何一個子節點的鍵值時為最年夜堆。 當父節點的鍵值老是小於或等於任何一個子節點的鍵值時為最小堆。
下圖是一個最年夜堆
priorityQueue隊頭就是給定次序的最小元素。
priorityQueue不許可空值且不支撐non-comparable的對象。priorityQueue請求應用Comparable和Comparator接口給對象排序，而且在排序時會依照優先級處置個中的元素。
priorityQueue的年夜小是無窮制的（unbounded）, 但在創立時可以指定初始年夜小。當增長隊列元素時，隊列會主動擴容。
priorityQueue不是線程平安的， 相似的PriorityBlockingQueue是線程平安的。
我們曉得隊列是遵守先輩先出（First-In-First-Out）形式的，但有些時刻須要在隊列中基於優先級處置對象。舉個例子，比喻說我們有一個逐日生意業務時段生成股票申報的運用法式，須要處置年夜量數據而且消費許多處置時光。客戶向這個運用法式發送要求時，現實上就進入了隊列。我們須要起首處置優先客戶再處置通俗用戶。在這類情形下，Java的PriorityQueue(優先隊列)會很有贊助。
PriorityQueue是基於優先堆的一個無界隊列，這個優先隊列中的元素可以默許天然排序或許經由過程供給的Comparator（比擬器）在隊列實例化的時排序。
優先隊列不許可空值，並且不支撐non-comparable（弗成比擬）的對象，好比用戶自界說的類。優先隊列請求應用Java Comparable和Comparator接口給對象排序，而且在排序時會依照優先級處置個中的元素。
優先隊列的頭是基於天然排序或許Comparator排序的最小元素。假如有多個對象具有異樣的排序，那末便可能隨機地取個中隨意率性一個。當我們獲得隊列時，前往隊列的頭對象。
優先隊列的年夜小是不受限制的，但在創立時可以指定初始年夜小。當我們向優先隊列增長元素的時刻，隊列年夜小會主動增長。
PriorityQueue長短線程平安的，所以Java供給了PriorityBlockingQueue（完成BlockingQueue接口）用於Java多線程情況。
2、PriorityQueue源碼剖析
成員：
priavte transient Object[] queue; private int size = 0;
1.PriorityQueue結構小頂堆的進程
這裡我們以priorityQueue結構器傳入一個容器為參數PriorityQueue(Collecntion<? extends E>的例子：
結構小頂堆的進程年夜體分兩步：
復制容器數據，檢討容器數據能否為null
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;
}
調劑，使數據知足小頂堆的構造。
起首引見兩個調劑方法siftUp和siftDown
siftDown: 在給定初始化元素的時刻，要調劑元素，使其知足最小堆的構造性質。是以一直地從上到下將元素x的鍵值與孩子比擬並做交流，直到找到元素x的鍵值小於等於孩子的鍵值（即包管它比其閣下結點值小），或許是降低到葉子節點為止。
例如以下的表示圖，調劑9這個節點：
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // size/2是第一個葉子結點的下標
//只需沒到葉子節點
while (k < half) {
int child = (k << 1) + 1; // 左孩子
Object c = queue[child];
int right = child + 1;
//找出閣下孩子中小的誰人
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每次新增長一個元素的時刻是將新元素拔出對尾的。是以，應當與siftDown有異樣的調劑進程，只不外是從下（葉子）往上調劑。
例如以下的表示圖，填加key為3的節點：
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1; //獲得parent下標
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
整體的樹立小頂堆的進程就是：
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
個中heapify就是siftDown的進程。
2.PriorityQueue容量擴容進程
從實例成員可以看出，PriorityQueue保護了一個Object[], 是以它的擴容方法跟次序表ArrayList相差不多。
這裡只給出grow辦法的源碼
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);
}
可以看出，當數組的Capacity不年夜的時刻，每次擴容也不年夜。當數組容量年夜於64的時刻，每次擴容double。
3、PriorityQueue的運用
eg1：
這裡給出一個最簡略的運用：從靜態數據中求第K個年夜的數。
思緒就是保持一個size = k 的小頂堆。
//data是靜態數據
//heap保持靜態數據的堆
//res用來保留第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：
我們有一個用戶類Customer，它沒有供給任何類型的排序。當我們用它樹立優先隊列時，應當為其供給一個比擬器對象。
Customer.java
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隨機數生成隨機用戶對象。關於天然排序，我們應用Integer對象，這也是一個封裝過的Java對象。
上面是終究的測試代碼，展現若何應用PriorityQueue：
PriorityQueueExample.java
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) {
//優先隊列天然排序示例
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);
}
//優先隊列應用示例
Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
addDataToQueue(customerPriorityQueue);
pollDataFromQueue(customerPriorityQueue);
}
//匿名Comparator完成
public static Comparator<Customer> idComparator = new Comparator<Customer>(){
@Override
public int compare(Customer c1, Customer c2) {
return (int) (c1.getId() - c2.getId());
}
};
//用於往隊列增長數據的通用辦法
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));
}
}
//用於從隊列取數據的通用辦法
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());
}
}
}
留意我用完成了Comparator接口的Java匿名類，而且完成了基於id的比擬器。
當我運轉以上測試法式時，我獲得以下輸入：
Processing Integer:9 Processing Integer:16 Processing Integer:18 Processing Integer:25 Processing Integer:33 Processing Integer:75 Processing Integer:77 Processing Customer with ID=6 Processing Customer with ID=20 Processing Customer with ID=24 Processing Customer with ID=28 Processing Customer with ID=29 Processing Customer with ID=82 Processing Customer with ID=96
從輸入成果可以清晰的看到，最小的元素在隊列的頭部因此最早被掏出。假如不完成Comparator，在樹立customerPriorityQueue時會拋出ClassCastException。
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)
