本來想自己寫的油额，網上查找資料逞泄，發(fā)現(xiàn)這篇 給 jdk 寫注釋系列之 jdk1.6 容器(12)-PriorityQueue 源碼解析 文章寫的很詳細担租，思路清晰。自己再寫估計也達不到原文的水平鲫构，于是直接轉載原文了浓恶。
PriorityQueue 是一種什么樣的容器呢？看過前面的幾個 jdk 容器分析的話结笨，看到 Queue 這個單詞你一定會包晰，哦~ 這是一種隊列。是的炕吸，PriorityQueue 是一種隊列伐憾，但是它又是一種什么樣的隊列呢？它具有著什么樣的特點呢赫模？它的底層實現(xiàn)方式又是怎么樣的呢树肃？我們一起來看一下。
PriorityQueue 其實是一個優(yōu)先隊列瀑罗，什么是優(yōu)先隊列呢胸嘴？這 和我們前面講的先進先出（First In First Out ）的隊列的區(qū)別在于，優(yōu)先隊列每次出隊的元素都是優(yōu)先級最高的元素斩祭。那么怎么確定哪一個元素的優(yōu)先級最高呢劣像，jdk 中使用堆這么一種數據結構，通過堆使得每次出隊的元素總是隊列里面最小的摧玫，而元素的大小比較方法可以由用戶指定耳奕，這里就相當于指定優(yōu)先級嘍。
1. 二叉堆介紹
那么堆又是什么一種數據結構呢诬像、它有什么樣的特點呢屋群？（以下見于百度百科）
- 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
- 堆總是一棵完全樹颅停。
常見的堆有二叉堆谓晌、斐波那契堆等。而 PriorityQueue 使用的便是二叉堆癞揉，這里我們主要來分析和學習二叉堆。
二叉堆是一種特殊的堆溺欧，二叉堆是完全二叉樹或者是近似完全二叉樹喊熟。二叉堆有兩種：最大堆和最小堆。最大堆：父結點的鍵值總是大于或等于任何一個子節(jié)點的鍵值姐刁；最小堆：父結點的鍵值總是小于或等于任何一個子節(jié)點的鍵值芥牌。
說到二叉樹我們就比較熟悉了，因為我們前面分析和學習過了二叉查找樹和紅黑樹（TreeMap）聂使。慣例壁拉，我們以最小堆為例谬俄，用圖解來描述下什么是二叉堆。
上圖就是一顆完全二叉樹（二叉堆）弃理，我們可以看出什么特點嗎溃论，那就是在第 n 層深度被填滿之前，不會開始填第 n+1 層深度痘昌，而且元素插入是從左往右填滿钥勋。
基于這個特點，二叉堆又可以用數組來表示而不是用鏈表辆苔，我們來看一下：
通過 "用數組表示二叉堆" 這張圖算灸，我們可以看出什么規(guī)律嗎？那就是驻啤，基于數組實現(xiàn)的二叉堆菲驴，對于數組中任意位置的 n 上元素，其左孩子在 [2n+1] 位置上骑冗，右孩子 [2(n+1)] 位置赊瞬，它的父親則在 [(n-1)/2] 上，而根的位置則是[0]
好了沐旨、在了解了二叉堆的基本概念后森逮，我們來看下 jdk 中 PriorityQueue 是怎么實現(xiàn)的。
2. PriorityQueue 的底層實現(xiàn)
先來看下 PriorityQueue 的定義：
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
我們看到 PriorityQueue 繼承了 AbstractQueue 抽象類磁携，并實現(xiàn)了 Serializable 接口褒侧，AbstractQueue 抽象類實現(xiàn)了 Queue 接口，對其中方法進行了一些通用的封裝谊迄，具體就不多看了闷供。
下面再看下 PriorityQueue 的底層存儲相關定義：
// 默認初始化大小
privatestaticfinalintDEFAULT_INITIAL_CAPACITY = 11;
// 用數組實現(xiàn)的二叉堆，下面的英文注釋確認了我們前面的說法统诺。
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
private transient Object[] queue ;
// 隊列的元素數量
private int size = 0;
// 比較器
private final Comparator<? super E> comparator;
// 修改版本
private transient int modCount = 0;
我們看到 jdk 中的 PriorityQueue 的也是基于數組來實現(xiàn)一個二叉堆歪脏，并且注釋中解釋了我們前面的說法。而 Comparator 這個比較器我們已經很熟悉了粮呢，我們說 PriorityQueue 是一個有限隊列婿失，他可以由用戶指定優(yōu)先級，就是靠這個比較器嘍啄寡。
3. PriorityQueue 的構造方法
/**
* 默認構造方法豪硅，使用默認的初始大小來構造一個優(yōu)先隊列，比較器 comparator 為空挺物，這里要求入隊的元素必須實現(xiàn) Comparator 接口
*/
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* 使用指定的初始大小來構造一個優(yōu)先隊列懒浮，比較器 comparator 為空，這里要求入隊的元素必須實現(xiàn) Comparator 接口
*/
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
/**
* 使用指定的初始大小和比較器來構造一個優(yōu)先隊列
*/
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
// 初始大小不允許小于 1
if (initialCapacity < 1)
throw new IllegalArgumentException();
// 使用指定初始大小創(chuàng)建數組
this.queue = new Object[initialCapacity];
// 初始化比較器
this.comparator = comparator;
}
/**
* 構造一個指定 Collection 集合參數的優(yōu)先隊列
*/
public PriorityQueue(Collection<? extends E> c) {
// 從集合 c 中初始化數據到隊列
initFromCollection(c);
// 如果集合 c 是包含比較器 Comparator 的 (SortedSet/PriorityQueue)识藤，則使用集合 c 的比較器來初始化隊列的 Comparator
if (c instanceof SortedSet)
comparator = (Comparator<? super E>)
((SortedSet<? extends E>)c).comparator();
else if (c instanceof PriorityQueue)
comparator = (Comparator<? super E>)
((PriorityQueue<? extends E>)c).comparator();
// 如果集合 c 沒有包含比較器砚著，則默認比較器 Comparator 為空
else {
comparator = null;
// 調用 heapify 方法重新將數據調整為一個二叉堆
heapify();
}
}
/**
* 構造一個指定 PriorityQueue 參數的優(yōu)先隊列
*/
public PriorityQueue(PriorityQueue<? extends E> c) {
comparator = (Comparator<? super E>)c.comparator();
initFromCollection(c);
}
/**
* 構造一個指定 SortedSet 參數的優(yōu)先隊列
*/
public PriorityQueue(SortedSet<? extends E> c) {
comparator = (Comparator<? super E>)c.comparator();
initFromCollection(c);
}
/**
* 從集合中初始化數據到隊列
*/
private void initFromCollection(Collection<? extends E> c) {
// 將集合 Collection 轉換為數組 a
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
// 如果轉換后的數組 a 類型不是 Object 數組次伶，則轉換為 Object 數組
if (a.getClass() != Object[].class)
a = Arrays. copyOf(a, a.length, Object[]. class);
// 將數組 a 賦值給隊列的底層數組 queue
queue = a;
// 將隊列的元素個數設置為數組 a 的長度
size = a.length ;
}
構造方法還是比較容易理解的，第四個構造方法中稽穆，如果填入的集合 c 沒有包含比較器 Comparator冠王，則在調用 initFromCollection 初始化數據后，在調用 heapify 方法對數組進行調整秧骑，使得它符合二叉堆的規(guī)范或者特點版确，具體 heapify 是怎么構造二叉堆的，我們后面再看乎折。
那么怎么樣調整才能使一些雜亂無章的數據變成一個符合二叉堆的規(guī)范的數據呢绒疗？
4. 二叉堆的添加原理及 PriorityQueue 的入隊實現(xiàn)
我們回憶一下，我們在說紅黑樹 TreeMap 的時候說骂澄，紅黑樹為了維護其紅黑平衡吓蘑，主要有三個動作：左旋、右旋坟冲、著色磨镶。那么二叉堆為了維護他的特點又需要進行什么樣的操作呢。
我們再來看下二叉堆（最小堆為例）的特點：
- 父結點的鍵值總是小于或等于任何一個子節(jié)點的鍵值健提。
- 基于數組實現(xiàn)的二叉堆琳猫，對于數組中任意位置的 n 上元素，其左孩子在 [2n+1] 位置上私痹，右孩子 [2(n+1)] 位置脐嫂，它的父親則在 [n-1/2] 上，而根的位置則是[0]紊遵。
為了維護這個特點账千，二叉堆在添加元素的時候，需要一個 "上移" 的動作暗膜，什么是 "上移" 呢匀奏，我們繼續(xù)用圖來說明。
結合上面的圖解学搜，我們來說明一下二叉堆的添加元素過程：
- 將元素 2 添加在最后一個位置（隊尾）（圖 2）娃善。
- 由于 2 比其父親 6 要小，所以將元素 2 上移瑞佩，交換 2 和 6 的位置（圖 3）会放；
- 然后由于 2 比 5 小，繼續(xù)將 2 上移钉凌，交換 2 和 5 的位置（圖 4），此時 2 大于其父親（根節(jié)點）1捂人，結束御雕。
注：這里的節(jié)點顏色是為了凸顯矢沿，應便于理解，跟紅黑樹的中的顏色無關酸纲，不要弄混捣鲸。。闽坡。
看完了這 4 張圖栽惶，是不是覺得二叉堆的添加還是挺容易的，那么下面我們具體看下 PriorityQueue 的代碼是怎么實現(xiàn)入隊操作的吧疾嗅。
/**
* 添加一個元素
*/
public boolean add(E e) {
return offer(e);
}
/**
* 入隊
*/
public boolean offer(E e) {
// 如果元素 e 為空外厂，則排除空指針異常
if (e == null)
throw new NullPointerException();
// 修改版本 + 1
modCount++;
// 記錄當前隊列中元素的個數
int i = size ;
// 如果當前元素個數大于等于隊列底層數組的長度，則進行擴容
if (i>= queue .length)
grow(i + 1);
// 元素個數 + 1
size = i + 1;
// 如果隊列中沒有元素代承，則將元素 e 直接添加至根（數組小標 0 的位置）
if (i == 0)
queue[0] = e;
// 否則調用 siftUp 方法汁蝶，將元素添加到尾部，進行上移判斷
else
siftUp(i, e);
return true;
}
jdk 中论悴，不是直接將根元素刪除掖棉，然后再將下面的元素做上移，重新補充根元素膀估；而是找出隊尾的元素幔亥，并在隊尾的位置上刪除，然后通過根元素的下移察纯，給隊尾元素找到一個合適的位置帕棉，最終覆蓋掉跟元素，從而達到刪除根元素的目的捐寥。這樣做在一些情況下笤昨，會比直接刪除在上移根元素，或者直接下移根元素再調整隊尾元素的位置少操作一些步奏（比如上面圖解中的例子握恳，不信你可以試一下 _）瞒窒。
明白了二叉堆的入隊和出隊操作后，其他的方法就都比較簡單了乡洼，下面我們再來看一個二叉堆中比較重要的過程崇裁，二叉堆的構造。
6. 堆的構造過程
我們在上面提到過的束昵，堆的構造是通過一個 heapify 方法拔稳，下面我們來看下 heapify 方法的實現(xiàn)。
/**
* Establishes the heap invariant (described above) in the entire tree,
* assuming nothing about the order of the elements prior to the call.
*/
private void heapify() {
for (int i = (size>>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
這個方法很簡單锹雏，就這幾行代碼巴比，但是理解起來卻不是那么容器的，我們來分析下。
假設有一個無序的數組轻绞，要求我們將這個數組建成一個二叉堆采记，你會怎么做呢？最簡單的辦法當然是將數組的數據一個個取出來政勃，調用入隊方法唧龄。但是這樣做，每次入隊都有可能會伴隨著元素的移動奸远，這么做是十分低效的既棺。那么有沒有更加高效的方法呢，我們來看下懒叛。
為了方便丸冕，我們將上面我們圖解中的數組去掉幾個元素，只留下 7芍瑞、6晨仑、5、12拆檬、10洪己、3、1竟贯、11答捕、15、4（順序已經隨機打亂）屑那。ok拱镐、那么接下來，我們就按照當前的順序建立一個二叉堆持际，暫時不用管它是否符合標準沃琅。
int a = [7, 6, 5, 12, 10, 3, 1, 11, 15, 4];
我們觀察下用數組 a 建成的二叉堆，很明顯蜘欲，對于葉子節(jié)點 4佛致、15秃殉、11共郭、1稽荧、3 來說，它們已經是一個合法的堆澈歉。所以只要最后一個節(jié)點的父節(jié)點展鸡，也就是最后一個非葉子節(jié)點 a[4]=10 開始調整，然后依次調整 a[3]=12埃难，a[2]=5莹弊，a[1]=6涤久，a[0]=7，分別對這幾個節(jié)點做一次 "下移" 操作就可以完成了堆的構造箱硕。ok拴竹，我們還是用圖解來分析下這個過程。
我們參照圖解分別來解釋下這幾個步奏：
- 對于節(jié)點 a[4]=10 的調整（圖 1）剧罩，只需要交換元素 10 和其子節(jié)點 4 的位置（圖 2）。
- 對于節(jié)點 a[3]=12 的調整座泳，只需要交換元素 12 和其最小子節(jié)點 11 的位置（圖 3）惠昔。
- 對于節(jié)點 a[2]=5 的調整，只需要交換元素 5 和其最小子節(jié)點 1 的位置（圖 4）挑势。
- 對于節(jié)點 a[1]=6 的調整镇防，只需要交換元素 6 和其最小子節(jié)點 4 的位置（圖 5）。
- 對于節(jié)點 a[0]=7 的調整潮饱，只需要交換元素 7 和其最小子節(jié)點 1 的位置来氧，然后交換 7 和其最小自己點 3 的位置（圖 6）。
至此香拉，調整完畢啦扬，建堆完成。
再來回顧一下凫碌，PriorityQueue 的建堆代碼扑毡，看看是否可以看得懂了。
private void heapify() {
for (int i = (size>>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
int i = (size>>> 1) - 1盛险，這行代碼是為了找尋最后一個非葉子節(jié)點瞄摊，然后倒序進行 "下移"siftDown 操作，是不是很顯然了苦掘。
到這里 PriorityQueue 的基本操作就分析完了换帜，明白了其底層二叉堆的概念及其入隊、出隊鹤啡、建堆等操作惯驼，其他的一些方法代碼就很簡單了，這里就不一一分析了揉忘。
PriorityQueue 完跳座！
參見：
給 jdk 寫注釋系列之 jdk1.6 容器 (11)-Queue 之 ArrayDeque 源碼解析
給 jdk 寫注釋系列之 jdk1.6 容器 (9)-Strategy 設計模式之 Comparable&Comparator 接口
