?????之前的文章中花盐，我們有介紹過動態(tài)數(shù)組ArrayList，雙向隊列LinkedList菇爪，鍵值對集合HashMap算芯，樹集TreeMap。他們都各自有各自的優(yōu)點凳宙，ArrayList動態(tài)擴容熙揍，數(shù)組實現(xiàn)查詢非常快但要求連續(xù)內存空間氏涩，雙向隊列LinkedList不需要像ArrayList一樣創(chuàng)建連續(xù)的內存空間届囚，它以鏈表的形式連接各個節(jié)點，但是查詢搜索效率極低是尖。HashMap存放鍵值對意系，內部使用數(shù)組加鏈表實現(xiàn)，檢索快但是由于鍵是按照Hash值存儲的饺汹，所以無序蛔添，在某些情況下不合適。TreeMap使用優(yōu)化了的排序二叉樹（紅黑樹）作為邏輯實現(xiàn)兜辞，物理實現(xiàn)使用一個靜態(tài)內部類Entry代表一個樹節(jié)點迎瞧，這是一個完全有序的結構，但是每個樹節(jié)點都需要保存一個父節(jié)點引用弦疮，左右孩子節(jié)點引用夹攒，還有一個value值，雖然效率高但開銷很大胁塞。
?????今天我們將要介紹的PriorityQueue優(yōu)先隊列咏尝，更多的可以理解為是上述所有集合實現(xiàn)的一種折中的結構，它邏輯上使用堆結構（完全二叉樹）實現(xiàn)啸罢，物理上使用動態(tài)數(shù)組實現(xiàn)编检，并非像TreeMap一樣完全有序，但是如果按照指定方式出隊扰才，結果可以是有序的允懂。本篇就將詳細談談該結構的內部實現(xiàn)，以下是涉及的主要內容：

• 堆數(shù)據(jù)結構的簡單介紹
• 構造PriorityQueue實例
• 有關優(yōu)先隊列的基本操作（增刪改查）
• 其他相關操作的細節(jié)
• 一個簡單的實例的應用

一衩匣、堆結構的簡單介紹
?????這里的堆是一種數(shù)據(jù)結構而非計算機內存中的堆棧蕾总。堆結構在邏輯上是完全二叉樹粥航，物理存儲上是數(shù)組。在介紹它之前生百，我們先了解完全二叉樹的相關知識递雀。首先我們知道，滿二叉樹除了葉子節(jié)點蚀浆，其余所有節(jié)點都具有左右孩子節(jié)點缀程，類似下圖：

這里寫圖片描述

整棵樹看起來是滿的，除了葉子節(jié)點沒有孩子節(jié)點外市俊，其余所有節(jié)點都是左右孩子節(jié)點的杨凑。而我們的完全二叉樹要求沒這么嚴格，它并不要求每個非葉子節(jié)點都具有左右孩子摆昧，但一定要按照從左到右的順序出現(xiàn)撩满，不能說沒有左孩子卻有右孩子。以下是幾個完全二叉樹：

這里寫圖片描述

但是以下幾個則不是完全二叉樹：

這里寫圖片描述

滿足完全二叉樹的前提是据忘，在同一層上鹦牛，前面的節(jié)點沒有孩子節(jié)點，后面節(jié)點就不能有孩子節(jié)點勇吊。正如上圖第一棵樹一樣曼追，只有2節(jié)點具有左右孩子節(jié)點之后，3節(jié)點才能具有孩子節(jié)點汉规。上圖第二棵樹為什么不滿足完全二叉樹礼殊，因為完全二叉樹中每個節(jié)點必須是先有左孩子節(jié)點然后才能有右孩子節(jié)點。如果你學習過數(shù)據(jù)結構针史，上述文字可能會幫助你快速回憶起來相關概念晶伦，但是如果你沒有學習過數(shù)據(jù)結構，那么你可能需要自行百度或者評論留言了解學習相關知識之后再繼續(xù)下文啄枕。

上述文字我們回顧了完全二叉樹的相關概念婚陪，但是完全二叉樹并不是堆結構，堆結構是不完全有序的完全二叉樹频祝。我們知道完全二叉樹有個非常大的優(yōu)點泌参，你可以從任意節(jié)點根據(jù)公式推算出該節(jié)點的左右孩子節(jié)點的位置以及父節(jié)點的位置。例如：

這里寫圖片描述

上圖中常空，我們?yōu)槊總€節(jié)點編號沽一，此時我們可以從任意一個節(jié)點推算出它的父節(jié)點，左右孩子節(jié)點的位置漓糙。例如：當前節(jié)點為4號節(jié)點铣缠，那么該節(jié)點的父節(jié)點編號為4/2，左孩子節(jié)點編號24，右孩子節(jié)點編號24+1蝗蛙。想必公式大家已經能夠得出蝇庭，當前節(jié)點位置為 i ，父節(jié)點位置 i/2捡硅，左孩子節(jié)點位置2i遗契，右孩子節(jié)點2i+1。利用這個特性病曾，我們就不必維護節(jié)點與節(jié)點之間的相互引用，TreeMap中定義一個Entry類漾根，分別一個parent引用泰涂，left引用，right引用辐怕，并使用它們維護當前節(jié)點和別的節(jié)點之間的關系逼蒙。而我們利用完全二叉樹的這種特性，完全可以用數(shù)組作為物理存儲寄疏。上述完全二叉樹可以存儲為以下的數(shù)組：

這里寫圖片描述

雖然數(shù)組中并沒有顯示出任何節(jié)點之間的關系是牢，但是他們之間的關系是隱含的。例如：5號節(jié)點的父節(jié)點編號5/2陕截，是2號驳棱，左右孩子節(jié)點分別為52，52+1節(jié)點农曲。

以上我們便完成了對堆結構的大致描述社搅，完全二叉樹加數(shù)組。下面我們簡單介紹堆結構中添加元素乳规，刪除元素是怎么做到保持堆結構不變的形葬。在詳細介紹之前，我們需要知道暮的，堆分大根堆和小根堆笙以。大根堆的要求是父節(jié)點比子節(jié)點的值大，小根堆要求父節(jié)點的值比子節(jié)點的值小冻辩，至于左右孩子節(jié)點的值的大小沒有要求猖腕，所以我們說堆是不完全有序結構。下文我們將主要以小根堆為例微猖，介紹堆結構中添加刪除元素是怎么做到保持這種結構不發(fā)生改變的谈息。

這里寫圖片描述

這是一個小根堆，假設我們現(xiàn)在要添加一個元素到該堆結構中凛剥。假定新元素的值為9侠仇，主要操作有以下兩個步驟：

• 將新元素添加到堆結構的末尾（不論該值的大小）
• 不斷調整直至滿足堆結構

第一步，添加新元素到堆結構末尾：

這里寫圖片描述

第二步逻炊，調整結構：

這里寫圖片描述

添加元素還是比較簡單的互亮，就兩個步驟。無論將要添加的新元素的值是多大余素，第一步始終是將該新元素添加到最后位置豹休，第二步可能不止一次的調整結構，但最終會調整完成桨吊，保持該堆結構威根。下面我們看刪除節(jié)點的不同情況。
1视乐、刪除頭節(jié)點

這里寫圖片描述

假定現(xiàn)在我們需要刪除頭部元素3洛搀，我們主要還是兩個步驟：

• 用最后一個元素替換頭部元素
• 用頭元素和兩個孩子中值較小的節(jié)點相比較，如果小于該節(jié)點的值則滿足堆結構佑淀，不做任何調整留美，否則交換之后做同樣的判斷

第一步，用尾部元素替換頭元素：

這里寫圖片描述

第二步伸刃，和較小值的子節(jié)點比較并完成交換：

這里寫圖片描述

這里寫圖片描述

最后刪除后的結果如上圖所示谎砾，刪除頭節(jié)點的情況還是比較簡單的，下面我們看從中間刪除元素捧颅。

2景图、刪除中間元素

這里寫圖片描述

現(xiàn)在假如我們需要刪除5號節(jié)點，主要是三個步驟：

• 用最后一個元素替換將要被刪除的元素并刪除最后元素
• 判斷該節(jié)點的值與其子節(jié)點中最小的值比較碉哑，如果小于最小值則維持堆結構症歇，否則向下調整
• 判斷該節(jié)點的值是否小于父節(jié)點的值，如果小于則向上調整谭梗，否則維持堆結構

第一步忘晤，用最后元素替換將要被刪除的元素：

這里寫圖片描述

第二步，與子節(jié)點比較判斷：

這里寫圖片描述

第三步激捏，與父節(jié)點比較设塔，滿足條件，維持堆結構远舅。
概括整個刪除的過程闰蛔，無論是從頭部刪除還是從中間刪除元素，都是先用最后的元素替換被刪元素图柏，然后向下調整來維持堆結構序六，接著向上調整維持堆結構。

至此蚤吹，我們簡單介紹了堆這種數(shù)據(jù)結構例诀，包括向其中添加刪除元素的時候随抠，它維持這種的結構的解決辦法。我們花了大量文筆介紹這種結構繁涂，是因為PriorityQueue就是對這種堆結構的實現(xiàn)拱她，只有理解了這種數(shù)據(jù)結構才能更好的理解PriorityQueue。下面我們開始看PriorityQueue的原理及具體實現(xiàn)的代碼扔罪。

二秉沼、構造PriorityQueue實例
?????在實際介紹PriorityQueue原理之前，再次啰嗦PriorityQueue的內部結構矿酵。PriorityQueue中的元素在邏輯上構成了一棵完全二叉樹唬复，但是在實際存儲時轉換為了數(shù)組保存在內存中，而我們的PriorityQueue繼承了接口Queue全肮，表名這是一個隊列盅抚，只是它不像普通隊列（例如：LinkedList）在遍歷輸出的時候簡單的按順序從頭到尾輸出，PriorityQueue總是先輸出根節(jié)點的值倔矾，然后調整樹使之繼續(xù)成為一棵完全二叉樹 樣每次輸出的根節(jié)點總是整棵樹優(yōu)先級最高的，要么數(shù)值最小要么數(shù)值最大柱锹。下面我們看如何構造一個PriorityQueue實例哪自。

在PriorityQueue的內部，主要有以下結構屬性構成：

//默認用于存儲節(jié)點信息的數(shù)組的大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//用于存儲節(jié)點信息的數(shù)組
transient Object[] queue;
//數(shù)組中實際存放元素的個數(shù)
private int size = 0;
//Comparator比較器
private final Comparator<? super E> comparator;
//用于記錄修改次數(shù)的變量
transient int modCount = 0;

我們知道禁熏，堆這種數(shù)據(jù)結構主要分類有兩種壤巷，大根堆和小根堆。而我們每次的調整結構都是不斷按照某種規(guī)則比較兩個元素的值大小瞧毙，然后調整結構胧华，這里就需要用到我們的比較器。所以構建一個PriorityQueue實例主要還是初始化數(shù)組容量和comparator比較器宙彪，而在PriorityQueue主要有以下幾種構造器：

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

主要構造器有上述四種矩动，前三種在內部會調用最后一個構造器。兩個參數(shù)释漆，一個指定要初始化數(shù)組的容量悲没，一個則用于初始化一個比較器。如果沒有顯式指定他們的值男图，則對于容量則默認為DEFAULT_INITIAL_CAPACITY（11）示姿，comparator則為null。下面我們看獲取到PriorityQueue實例之后逊笆，如何向其中添加和刪除節(jié)點卻一樣保持原堆結構不變栈戳。

三、有關優(yōu)先隊列的基本操作（增刪改查）
?????首先我們看添加一個元素到堆結構中难裆，我們使用add或者offer方法完成新添一個元素到堆結構中子檀。

public boolean add(E e) {
   return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
   size = i + 1;
   if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

實際上add方法的內部調用的還是offer方法，所以我們主要看看offer是如何實現(xiàn)添加一個元素到堆結構中并維持這種結構不被破壞的。首先該方法定義了一 變量獲取queue中實際存放的元素個數(shù)命锄，緊接著一個if判斷堰乔，如果該數(shù)組已經被完全使用了（沒有可用空間了），會調用grow方法進行擴容脐恩，grow方法會根據(jù)具體情況判斷镐侯，如果原數(shù)組較小則會擴大兩倍，否則增加50%容量驶冒，由于具體代碼比較清晰苟翻，此處不再贅述。接著判斷該完全二叉樹是否為空骗污，如果沒有任何節(jié)點崇猫，那么直接將新增節(jié)點作為根節(jié)即可，否則會調用siftUp添加新元素并調整結構需忿，所以該方法是重點诅炉。

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

此處會根據(jù)調用者是否傳入比較器而分為兩種情況，代碼類似屋厘，我們只看一種即可涕烧。

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

該方法首先獲取最后一個位置的父節(jié)點的索引，然后定義變量接受父節(jié)點的值汗洒，如果新增的節(jié)點值和父節(jié)點的值比較之后滿足堆結構议纯，則直接break返回，否則循環(huán)向上交換溢谤，最終完成堆結構調整瞻凤。具體我們通過一個實例演示整個過程：

這里寫圖片描述

首先初始化一個小根堆，假如現(xiàn)在我們要添加一個新元素值為5世杀，根據(jù)siftUpUsingComparator方法的代碼阀参，此時參數(shù)k的值應為6，那么最后一個節(jié)點的父節(jié)點的索引為2（即三號節(jié)點11）瞻坝，然后e的值就為11结笨，通過比較器比較判斷5是否小于e，如果小于則說明需要調整結構湿镀，那么會將最后一個節(jié)點的值用父節(jié)點e的值取代炕吸，也就是會變成這個樣子：

這里寫圖片描述

再次進入循環(huán)，parent 的值為（2-1）/2=0勉痴，比較器比較索引為0的節(jié)點和我們需要新插入的節(jié)點（值為5）赫模，發(fā)現(xiàn)3小于5，則break出循環(huán)蒸矛，最后將queue[k] = x;瀑罗，最終結果如下：

這里寫圖片描述

以上就完成了新添一個元素到堆結構中并保持堆結構不被破壞胸嘴，可能上述文字在有些地方描述不清，但是相信大致意思應該是表達出來了斩祭，大家可以自行查看源碼感受下劣像。下面我們簡單看看刪除一個節(jié)點的代碼部分：

private E removeAt(int i) {
    modCount++;
    int s = --size;
    if (s == i) 
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

該方法內部也調用了多個其他方法，此處為了節(jié)約篇幅摧玫，大致說明下整個刪除過程耳奕，具體代碼大家可以自行體會。首先該方法會獲取到最后一個節(jié)點的索引并判斷刪除元素是否為最后一個節(jié)點诬像，如果是則直接刪除即可屋群。

如果刪除索引不是最后一個位置，那么首先會獲取到最后一個節(jié)點的值并將其刪除坏挠，緊接著將最后一個節(jié)點的值覆蓋掉待刪位置的節(jié)點值并調整結構芍躏，調整完成之后，會判斷queue[i] == moved降狠，如果為true表示新增元素之后并沒有調整結構（滿足堆結構）对竣，那么就會向上調整結構。（如果向下調整過結構自然是不需要再向上調整了）榜配，如果queue[i] != moved值為true表示向上調整過結構否纬，那么將會返回moved。（至于為什么要在向上調整結構之后返回moved芥牌，主要是用于迭代器使用，此處暫時不會介紹）聂使。

這里就是刪除一個節(jié)點的大致過程壁拉，該方法還是比較底層的，其實PriorityQueue中是有一些其他刪除節(jié)點的方法的柏靶，但是他們內部調用的幾乎都是removeAt這個方法弃理。例如：

//根據(jù)值刪除節(jié)點
public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

當然如果一個隊列中有多個具有重復值的節(jié)點，那么該方法調用了indexOf方法會獲取第一個符合條件的節(jié)點并刪除屎蜓。當然還有其他一些刪除方法痘昌，此處不再介紹，大家可以自行體會炬转。

四辆苔、有序出隊
?????我們說過，PriorityQueue這種結構使用的是堆結構扼劈，所以他是一種不完全有序的結構驻啤，但是我們也提過，可以逐個出隊來實現(xiàn)有序輸出荐吵。下面我們看看它是如何實現(xiàn)的：

public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}

上述我們列出了兩個方法的源碼骑冗，peek方法表示獲取隊列隊頭元素赊瞬，代碼還是容易的，我們主要看poll方法贼涩，該方法用于出隊頭節(jié)點并維持堆結構巧涧。

有了之前的基礎，poll方法的代碼還是簡單的遥倦，首先判斷該隊中是否有元素谤绳，如果沒有則直接返回null，否則分別獲取頭節(jié)點的值和末節(jié)點的值谊迄，刪除尾節(jié)點并將尾節(jié)點的值替換頭節(jié)點的值闷供，接著向下調整結構，最后返回被刪除的頭節(jié)點的值统诺。下面我們看一個實例：

public static void main(String[] args){
    PriorityQueue pq = new PriorityQueue();
    pq.offer(1);
    pq.offer(21);
    pq.offer(345);
    pq.offer(23);
    pq.offer(22);
    pq.offer(44);
    pq.offer(0);
    pq.offer(34);
    pq.offer(2);
    while(pq.peek()!=null){
        System.out.print(pq.poll() + " ");
    }
}

我們亂序添加一些元素到隊列中歪脏，當然每次添加都會維持堆結構，然后我們循環(huán)輸出粮呢。程序運行結果如下：

這里寫圖片描述

當然這里我們沒有顯式的傳入比較器婿失，此處會默認使用Integer的comparator，如果我們需要自己控制比較方式啄寡，可以傳入一個comparator用于比較豪硅。例如：

public static void main(String[] args){
   PriorityQueue pq = new PriorityQueue(
           new Comparator() {
               @Override
               public int compare(Object o1, Object o2) {
                   if((Integer)o1<=(Integer)o2){
                       return 1;
                   }
                   else
                       return -1;
               }
           }
   );

   pq.offer(1);
   pq.offer(22);
   pq.offer(4);
   pq.offer(45);
   pq.offer(12);
   pq.offer(5);
   pq.offer(76);
   pq.offer(34);
   pq.offer(23);
   pq.offer(22);
   while(pq.peek()!=null){
       System.out.print(pq.poll() + " ");
   }
}

以上代碼在構建PriorityQueue實例對象的時候顯式傳入一個comparator比較器，按照從大到小的順序構建一個堆結構挺物。輸出結果如下：

這里寫圖片描述

至此我們完成了對PriorityQueue這種堆結構的容器的簡單介紹懒浮，至于在何種情況下選擇該結構還需結合實際需求，總結不到之處识藤，望大家補充砚著！