一、什么是優(yōu)先級隊(duì)列

1、概念

我們都知道隊(duì)列，隊(duì)列的核心思想就是先進(jìn)先出，這個(gè)優(yōu)先級隊(duì)列有點(diǎn)不太一樣。優(yōu)先級隊(duì)列中，數(shù)據(jù)按關(guān)鍵詞有序排列，插入新數(shù)據(jù)的時(shí)候，會自動插入到合適的位置保證隊(duì)列有序。（順序有兩種形式：升序或者是降序）

來一個(gè)標(biāo)準(zhǔn)點(diǎn)的定義：

PriorityQueue類在Java1.5中引入。PriorityQueue是基于優(yōu)先堆的一個(gè)無界隊(duì)列，這個(gè)優(yōu)先隊(duì)列中的元素可以默認(rèn)自然排序或者通過提供的Comparator（比較器）在隊(duì)列實(shí)例化的時(shí)排序。要求使用Java Comparable和Comparator接口給對象排序，并且在排序時(shí)會按照優(yōu)先級處理其中的元素。

比如我們往隊(duì)列里面插入132，插入2的時(shí)候，就會在內(nèi)部調(diào)整為123（默認(rèn)順序是升序）。正是由于這個(gè)優(yōu)良特性可以幫助我們實(shí)現(xiàn)一系列問題。我們先看一個(gè)例子，體會一下他的優(yōu)點(diǎn)，然后再看一下為什么能夠?qū)崿F(xiàn)這樣的功能。

我們看到就算是我們隨意插入數(shù)據(jù)，但是輸出的結(jié)果總是有序的，這樣一來優(yōu)先級隊(duì)列就可以有了很多個(gè)使用場景。

招納?賢士

Join us

還有一種特殊的隊(duì)列叫做PriorityQueue，即優(yōu)先隊(duì)列。優(yōu)先隊(duì)列的作用是能保證每次取出的元素都是隊(duì)列中權(quán)值最小的（Java的優(yōu)先隊(duì)列每次取最小元素，C++的優(yōu)先隊(duì)列每次取最大元素）。這里牽涉到了大小關(guān)系，元素大小的評判可以通過元素本身的自然順序（natural ordering），也可以通過構(gòu)造時(shí)傳入的比較器（Comparator，類似于C++的仿函數(shù)）。

Java中PriorityQueue實(shí)現(xiàn)了Queue接口，不允許放入null元素；其通過堆實(shí)現(xiàn)，具體說是通過完全二叉樹（complete binary tree）實(shí)現(xiàn)的小頂堆（任意一個(gè)非葉子節(jié)點(diǎn)的權(quán)值，都不大于其左右子節(jié)點(diǎn)的權(quán)值），也就意味著可以通過數(shù)組來作為PriorityQueue的底層實(shí)現(xiàn)。

上圖中我們給每個(gè)元素按照層序遍歷的方式進(jìn)行了編號，如果你足夠細(xì)心，會發(fā)現(xiàn)父節(jié)點(diǎn)和子節(jié)點(diǎn)的編號是有聯(lián)系的，更確切的說父子節(jié)點(diǎn)的編號之間有如下關(guān)系：

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

通過上述三個(gè)公式，可以輕易計(jì)算出某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)以及子節(jié)點(diǎn)的下標(biāo)。這也就是為什么可以直接用數(shù)組來存儲堆的原因。

PriorityQueue的peek()和element操作是常數(shù)時(shí)間，add(), offer(), 無參數(shù)的remove()以及poll()方法的時(shí)間復(fù)雜度都是log(N)。

冬盡今宵長

先講使用，再講原理

隊(duì)列是遵循先進(jìn)先出（First-In-First-Out）模式的，但有時(shí)需要在隊(duì)列中基于優(yōu)先級處理對象。

舉兩個(gè)例子：

作業(yè)系統(tǒng)中的調(diào)度程序，當(dāng)一個(gè)作業(yè)完成后，需要在所有等待調(diào)度的作業(yè)中選擇一個(gè)優(yōu)先級最高的作業(yè)來執(zhí)行，并且也可以添加一個(gè)新的作業(yè)到作業(yè)的優(yōu)先隊(duì)列中。

每日交易時(shí)段生成股票報(bào)告的應(yīng)用程序中，需要處理大量數(shù)據(jù)并且花費(fèi)很多處理時(shí)間。客戶向這個(gè)應(yīng)用程序發(fā)送請求時(shí)，實(shí)際上就進(jìn)入了隊(duì)列。我們需要首先處理優(yōu)先客戶再處理普通用戶。在這種情況下，Java的PriorityQueue(優(yōu)先隊(duì)列)會很有幫助。

PriorityQueue類在Java1.5中引入并作為 Java Collections Framework 的一部分。PriorityQueue是基于優(yōu)先堆的一個(gè)無界隊(duì)列，這個(gè)優(yōu)先隊(duì)列中的元素可以默認(rèn)自然排序或者通過提供的Comparator（比較器）在隊(duì)列實(shí)例化的時(shí)排序。

優(yōu)先隊(duì)列不允許空值，而且不支持non-comparable（不可比較）的對象，比如用戶自定義的類。優(yōu)先隊(duì)列要求使用Java Comparable和Comparator接口給對象排序，并且在排序時(shí)會按照優(yōu)先級處理其中的元素。

優(yōu)先隊(duì)列的頭是基于自然排序或者Comparator排序的最小元素。如果有多個(gè)對象擁有同樣的排序，那么就可能隨機(jī)地取其中任意一個(gè)。當(dāng)我們獲取隊(duì)列時(shí)，返回隊(duì)列的頭對象。

優(yōu)先隊(duì)列的大小是不受限制的，但在創(chuàng)建時(shí)可以指定初始大小。當(dāng)我們向優(yōu)先隊(duì)列增加元素的時(shí)候，隊(duì)列大小會自動增加。

PriorityQueue是非線程安全的，所以Java提供了PriorityBlockingQueue（實(shí)現(xiàn)BlockingQueue接口）用于Java多線程環(huán)境。

我們有一個(gè)用戶類Customer，它沒有提供任何類型的排序。當(dāng)我們用它建立優(yōu)先隊(duì)列時(shí)，應(yīng)該為其提供一個(gè)比較器對象。

冬盡今宵長

實(shí)現(xiàn)原理：

Java中PriorityQueue通過二叉小頂堆實(shí)現(xiàn)，可以用一棵完全二叉樹表示（任意一個(gè)非葉子節(jié)點(diǎn)的權(quán)值，都不大于其左右子節(jié)點(diǎn)的權(quán)值），也就意味著可以通過數(shù)組來作為PriorityQueue的底層實(shí)現(xiàn)。

上圖中我們給每個(gè)元素按照層序遍歷的方式進(jìn)行了編號，如果你足夠細(xì)心，會發(fā)現(xiàn)父節(jié)點(diǎn)和子節(jié)點(diǎn)的編號是有聯(lián)系的，更確切的說父子節(jié)點(diǎn)的編號之間有如下關(guān)系：

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

通過上述三個(gè)公式，可以輕易計(jì)算出某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)以及子節(jié)點(diǎn)的下標(biāo)。這也就是為什么可以直接用數(shù)組來存儲堆的原因。

PriorityQueue的peek()和element操作是常數(shù)時(shí)間，add(), offer(), 無參數(shù)的remove()以及poll()方法的時(shí)間復(fù)雜度都是log(N)。

2、案例演示特性

Leetcode215題：在未排序的數(shù)組中找到第?k個(gè)最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。

輸入：3,2,3,1,2,4,5,5,6，k = 4。輸出就是5，因此重復(fù)的并不考慮。我們一般情況下一般首先想到冒泡排序。每一次都冒出來一個(gè)最小的元素，這樣冒K次，就是我們想要的結(jié)果。

其實(shí)冒泡排序還可以解決另外一個(gè)問題，那就是返回倒數(shù)第K大的元素，方法是每次冒出來一個(gè)最大的元素即可。

這樣做很簡單，但是需要我們自己手寫冒泡排序，下面我們看使用優(yōu)先級隊(duì)列如何解決的。

就這幾行代碼就搞定了，是不是超級簡單。為什么優(yōu)先級隊(duì)列能夠?qū)崿F(xiàn)呢？下面我們來分析一下他的數(shù)據(jù)結(jié)構(gòu)：

3、數(shù)據(jù)結(jié)構(gòu)

優(yōu)先級隊(duì)列底層的數(shù)據(jù)結(jié)構(gòu)其實(shí)是一顆二叉堆，什么是二叉堆呢？我們來看看

在這里我們會發(fā)現(xiàn)以下特征：

（1）二叉堆是一個(gè)完全二叉樹

（2）根節(jié)點(diǎn)總是大于左右子節(jié)點(diǎn)（大頂堆），或者是小于左右子節(jié)點(diǎn)（小頂堆）。

如果我們要插入一個(gè)節(jié)點(diǎn)怎么辦呢？

自己使用畫圖工具畫的，能看懂就行，不要在意那些細(xì)節(jié)兄弟。過程如下：

（1）找到待插入位置：滿足完全二叉樹的特點(diǎn)，依次插入

（2）插入之后判斷是否滿足二叉堆的性質(zhì)，不滿足那就調(diào)整

（3）1<==>6交換，發(fā)現(xiàn)不滿足，1<==>4交換，滿足即停止。

對于我們的優(yōu)先級隊(duì)列就是這樣的一種數(shù)據(jù)結(jié)構(gòu)，因此我們在插入的時(shí)候保證了數(shù)據(jù)的有序性。

OK。到這基本上我們能夠體會到優(yōu)先級隊(duì)列的思想了。來一個(gè)小結(jié)：

優(yōu)先級隊(duì)列使用二叉堆的特點(diǎn)，可以使得插入的數(shù)據(jù)自動排序（升序或者是降序）。

冬盡今宵長

源碼分析一般的順序都是先類屬性、構(gòu)造方法、普通方法。在編譯器中鼠標(biāo)定位到這個(gè)PriorityQueue上，ctrl+鼠標(biāo)左鍵就可以進(jìn)入到這個(gè)集合的源碼里面。

1、屬性

2、構(gòu)造方法

（1）默認(rèn)構(gòu)造方法：PriorityQueue()

使用默認(rèn)的初始容量（11）創(chuàng)建一個(gè) PriorityQueue，并根據(jù)其自然順序?qū)υ剡M(jìn)行排序。

（2）包含集合元素：PriorityQueue(Collection c)

創(chuàng)建包含指定 collection 中元素的 PriorityQueue。

（3）指定初始容量：PriorityQueue(int initialCapacity)

使用指定的初始容量創(chuàng)建一個(gè) PriorityQueue，并根據(jù)其自然順序?qū)υ剡M(jìn)行排序。

（4）指定初始容量和比較器：PriorityQueue(int initialCapacity, Comparator comparator)

使用指定的初始容量創(chuàng)建一個(gè) PriorityQueue，并根據(jù)指定的比較器對元素進(jìn)行排序。

（5）包含優(yōu)先級元素：PriorityQueue(PriorityQueue c)

創(chuàng)建包含指定優(yōu)先級隊(duì)列元素的 PriorityQueue。

（6）包含set元素：PriorityQueue(SortedSet c)

創(chuàng)建包含指定有序 set 元素的 PriorityQueue。

3、普通方法

PriorityQueue中常用的方法很多。來看幾個(gè)常用的。

（1）add：插入一個(gè)元素，不成功會拋出異常

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

我們看到add方法其實(shí)是通過調(diào)用offer方法實(shí)現(xiàn)的。我們直接看offer方法

（2）offer：插入一個(gè)元素，不能被立即執(zhí)行的情況下會返回一個(gè)特殊的值（true 或者 false）

注意，優(yōu)先級隊(duì)列插入的元素不能為空，這一點(diǎn)在文章一開始提到過。步驟是這樣的：

首先把modCount數(shù)量加1，如果容量不夠把當(dāng)前隊(duì)列的尺寸加1，最后在i的位置上使用siftUp方法把e添加進(jìn)來。此時(shí)真正插入的操作又落到了siftUp方法身上，我們接著看。

尼瑪，這里也沒有實(shí)現(xiàn)真正的插入操作，而是先判斷是否使用了自己的比較器。我們直接來看自己的比較器不為空，如何插入。

這里就是真正的插入操作了。一個(gè)正常的數(shù)據(jù)插入過程。沒什么特別的。

（3）remove：刪除一個(gè)元素，如果不成功會返回false。

這里會發(fā)現(xiàn)真正實(shí)現(xiàn)刪除操作的是removeAt方法。我們跟進(jìn)去看看

這個(gè)刪除操作主要是兩部分，if里面判斷刪除的是否是最后一個(gè)，否則的話就是用siftDown方法進(jìn)行“向下沉”刪除。不成功那就使用“向上浮”。

刪除的時(shí)候同樣需要進(jìn)行判斷比較器。

OK。刪除操作就是這么多?；舅悸肥窍蛏细∵€是向下沉。

（4）poll：刪除一個(gè)元素，并返回刪除的元素

又回到了siftDown刪除操作，就不贅述了。

（5）peek：查詢隊(duì)頂元素

（6）indexOf(Object o)：查詢對象o的索引

（7）contain(Object o)：判斷是否容納了元素

實(shí)現(xiàn)原理很簡單和上面的一樣。

總結(jié)：

1.這個(gè)PriorityQueue也是集合里面的，但是在開發(fā)中我們一般很少會用到，但是他的底層實(shí)現(xiàn)和思維值我們學(xué)習(xí)。

2.隊(duì)列是遵循先進(jìn)先出（First-In-First-Out）模式的，但有時(shí)需要在隊(duì)列中基于優(yōu)先級處理對象，加深了對于隊(duì)列的理解

3.現(xiàn)在堅(jiān)持自律，鍛煉身體，多學(xué)習(xí)，多敲代碼，加油！ヾ(?°?°?)??

? ? ? ? ?