解析Java中PriorityQueue優先級隊列結構的源碼及用法

一、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多線程環境。

二、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。

三、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: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

從輸出結果可以清楚的看到，最小的元素在隊列的頭部因而最先被取出。如果不實現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)