概述
??首先逢并，Priority翻譯之后是優(yōu)先級(jí)的意思之剧，而PriorityQueue，也就是優(yōu)先級(jí)隊(duì)列的意思砍聊。優(yōu)先級(jí)隊(duì)列背稼，和普通的先進(jìn)先出（FIFO）的隊(duì)列不同，優(yōu)先隊(duì)列每次取出的元素都是隊(duì)列中優(yōu)先級(jí)最高的玻蝌，而PriorityQueue默認(rèn)優(yōu)先級(jí)是取出元素最小的值蟹肘，當(dāng)然也可以按照我們指定的規(guī)則來(lái)自定義優(yōu)先級(jí)。
首先俯树，我們先看下官方API：https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
通過(guò)文檔帘腹，我們可以看到PriorityQueue優(yōu)先級(jí)隊(duì)列的一些性質(zhì)：
- PriorityQueue是基于優(yōu)先級(jí)堆來(lái)實(shí)現(xiàn)的無(wú)界優(yōu)先隊(duì)列，是在JDK1.5之后引入的類阳欲；
- 優(yōu)先隊(duì)列的元素按照它們的自然排序順序排列，或者根據(jù)使用的構(gòu)造方法提供的比較器來(lái)進(jìn)行排序陋率；
- 優(yōu)先隊(duì)列不允許null元素球化；
- 優(yōu)先隊(duì)列不允許插入非可比的對(duì)象，有可能會(huì)拋出ClassCastException瓦糟，比如對(duì)int排序筒愚，你添加了一個(gè)字符串類型的元素。
- 該優(yōu)先隊(duì)列每次取出的元素都是最小的菩浙。接口offer, poll, remove(),add方法巢掺，查詢時(shí)間都是O(log(n))，
- 優(yōu)先隊(duì)列迭代器迭代的順序無(wú)法保證劲蜻，如果想有序遍歷陆淀，請(qǐng)考慮使用Arrays.sort(priorityQueue.toArray())；而對(duì)于remove(Object) and contains(Object)方法斋竞，查詢是線性時(shí)間倔约；而對(duì)于peek, element, and size方法，查詢是常數(shù)時(shí)間坝初。
- 該優(yōu)先隊(duì)列不是線程安全的浸剩，如果要在線程安全的場(chǎng)景下使用钾军，建議使用線程安全的PriorityBlockingQueue類（優(yōu)先級(jí)阻塞隊(duì)列）；
??PriorityQueue是基于堆來(lái)實(shí)現(xiàn)的绢要，而堆這個(gè)數(shù)據(jù)結(jié)構(gòu)是怎樣的呢吏恭。我們來(lái)大概說(shuō)下，學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的應(yīng)該都知道重罪，堆是利用完全二叉樹(shù)來(lái)進(jìn)行處理數(shù)據(jù)樱哼，而完全二叉樹(shù)又是怎樣的呢。
??若二叉樹(shù)的深度是h剿配，那么除第h層外搅幅，其他各層（1～h-1）層的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊呼胚，這就是完全二叉樹(shù)茄唐。而堆就是基于這種數(shù)據(jù)結(jié)構(gòu)來(lái)處理數(shù)據(jù)的。我們用一張圖大致來(lái)看下完全二叉樹(shù)：
??如圖所示蝇更，圖1是完全二叉樹(shù)沪编，而圖二由于第三層所有的節(jié)點(diǎn)并非連續(xù)集中在最左側(cè)，所以不是完全二叉樹(shù)年扩；而圖三蚁廓，由于第三層的結(jié)點(diǎn)沒(méi)有達(dá)到最大個(gè)數(shù)（最大個(gè)數(shù)是4），所以也不是完全二叉樹(shù)厨幻。
其中堆一般還分為兩種：最大堆和最小堆相嵌。
- 顧名思義，最小堆就是根結(jié)點(diǎn)是所有數(shù)據(jù)中最小的元素克胳，并且堆中每個(gè)結(jié)點(diǎn)的值總是不大于其孩子結(jié)點(diǎn)的值平绩。
- 而最大堆就是根結(jié)點(diǎn)是所有結(jié)點(diǎn)中最大的元素，并且堆中每個(gè)結(jié)點(diǎn)的值總是不小于其孩子結(jié)點(diǎn)的值漠另。
??而PriorityQueue則是基于最小堆來(lái)實(shí)現(xiàn)的，并且底層是通過(guò)數(shù)組來(lái)構(gòu)建堆的數(shù)據(jù)結(jié)構(gòu)跃赚。由于本文的重點(diǎn)并不是堆亦或是完全二叉樹(shù)笆搓，所以堆的介紹就到這里來(lái)了。接下來(lái)我們來(lái)學(xué)習(xí)PriorityQueue的源碼纬傲。
繼承結(jié)構(gòu)及屬性
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
// 使用數(shù)組來(lái)構(gòu)造堆满败，也就是優(yōu)先級(jí)隊(duì)列
transient Object[] queue;
// 數(shù)組默認(rèn)的初始化容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 隊(duì)列的容量
private int size = 0;
// 比較器
private final Comparator<? super E> comparator;
// 結(jié)構(gòu)化修改次數(shù)
transient int modCount = 0;
// 數(shù)組最大容量限制，Integer最大值-8是說(shuō)一些虛擬機(jī)可能會(huì)在數(shù)組中保留一些header words的空間，
// 所以沒(méi)有取Integer最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
首先，PriorityQueue是繼承自AbstractQueue肤京，AbstractQueue則是實(shí)現(xiàn)了Queue接口稠茂，封裝了一些隊(duì)列基礎(chǔ)的方法或链。
- 優(yōu)先隊(duì)列底層使用數(shù)組來(lái)操作數(shù)據(jù)隙畜，并且數(shù)組的默認(rèn)初始化容量是11蒜埋，如果我們沒(méi)有指定比較器玖详，那系統(tǒng)將按照自然順序來(lái)構(gòu)建優(yōu)先隊(duì)列挖藏。
- 根據(jù)數(shù)組queue的注釋暑刃，我們可以知道，父節(jié)點(diǎn)與子節(jié)點(diǎn)的下標(biāo)值之間的關(guān)聯(lián)關(guān)系是：
childLeftNode= 2 * parentNode + 1;childRightNode= 2 * (parentNode + 1);膜眠，那么根據(jù)當(dāng)前結(jié)點(diǎn)計(jì)算父結(jié)點(diǎn)也很簡(jiǎn)單：parentNode = (thisNode - 1) / 2岩臣。
??Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+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.
比如依次調(diào)用PriorityQueue的add方法，放入：3宵膨，5架谎，7，1辟躏，9狐树，12，18鸿脓，7抑钟，6。畫(huà)了一張圖野哭，大概如下：
構(gòu)造方法
了解了優(yōu)先隊(duì)列的大致結(jié)構(gòu)及父子間關(guān)聯(lián)關(guān)系之后在塔，我們來(lái)看幾個(gè)常用的構(gòu)造方法。
/**
* 默認(rèn)構(gòu)造方法拨黔，初始化容量為11蛔溃，比較器為空
*/
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* 指定具體容量的構(gòu)造方法
*/
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
/**
* 指定比較器的構(gòu)造方法
*/
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
/**
* 指定容量和比較器的構(gò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
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* 將集合轉(zhuǎn)換為隊(duì)列篱蝇，根據(jù)集合類型不同贺待，又分為三種情況
*/
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
還有幾個(gè)構(gòu)造方法是是實(shí)現(xiàn)方式和上面這幾個(gè)差不多，就不一一貼上了零截。
方法
add方法
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
// 是否擴(kuò)容
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
首先麸塞，add方法內(nèi)部全是通過(guò)offer方法來(lái)實(shí)現(xiàn)的，我們來(lái)看一下offer方法的大致實(shí)現(xiàn)過(guò)程：
- 判空涧衙，添加數(shù)據(jù)不能為null哪工；
- 根據(jù)size與數(shù)組長(zhǎng)度比較，判斷是否擴(kuò)容弧哎；
- 判斷添加的是不是第一個(gè)元素雁比，如果不是，進(jìn)行調(diào)整撤嫩，增加完元素之后偎捎，我們需要進(jìn)行調(diào)整才能維護(hù)最大堆或最小堆的性質(zhì)。而這里的這個(gè)調(diào)整在堆中被稱為上浮（對(duì)應(yīng)的方法是siftUp）茴她。
grow方法
那么我們就接著來(lái)看擴(kuò)容方法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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
擴(kuò)容的時(shí)候，先判斷當(dāng)前隊(duì)列容量是否小于64败京，如果是擴(kuò)容一倍容量兜喻，如果不是，擴(kuò)容原容量的1/2赡麦。而hugeCapacity方法我們也看到多次了朴皆，參考List的擴(kuò)容就知道了，就是溢出檢查泛粹，而拷貝的方法也還是Arrays.copyOf方法遂铡。
siftUp方法
這個(gè)方法就是添加完元素之后進(jìn)行的上浮調(diào)整方法。
private void siftUp(int k, E x) {
// 是否有比較器
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
/**
* 如果有比較器晶姊，調(diào)用該方法扒接，內(nèi)部實(shí)現(xiàn)和siftUpComparable類似
*/
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;
}
/**
* 如果沒(méi)有比較器，調(diào)用該方法
*/
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
// k是下標(biāo)值们衙，保證結(jié)點(diǎn)有父級(jí)結(jié)點(diǎn)
while (k > 0) {
// 通過(guò)無(wú)符號(hào)右移钾怔，計(jì)算父級(jí)結(jié)點(diǎn)下標(biāo)，-> parent = (thisNode -1) / 2
int parent = (k - 1) >>> 1;
// 獲取父級(jí)結(jié)點(diǎn)的值
Object e = queue[parent];
// 比較要插入結(jié)點(diǎn)與父級(jí)結(jié)點(diǎn)值蒙挑，如果大于父級(jí)結(jié)點(diǎn)宗侦，不需要移動(dòng)，結(jié)束
if (key.compareTo((E) e) >= 0)
break;
// 如果小于父結(jié)點(diǎn)值忆蚀，父結(jié)點(diǎn)值下沉
queue[k] = e;
// 改變下標(biāo)值
k = parent;
}
// 最終將當(dāng)前結(jié)點(diǎn)值放到對(duì)應(yīng)的位置上
queue[k] = key;
}
通過(guò)代碼我們可以看到矾利，調(diào)整的方式是判斷是否有比較器，然后調(diào)用各自對(duì)應(yīng)的處理方法馋袜。
- 沒(méi)有比較器男旗，會(huì)按照我們添加的數(shù)據(jù)類型的比較器，也就是所謂的自然順序來(lái)進(jìn)行比較欣鳖。比如說(shuō)察皇，我們添加的數(shù)據(jù)類型是int，那么這里會(huì)按照Integer的Comparable來(lái)進(jìn)行排序观堂；
- 有比較器让网，按照對(duì)應(yīng)的比較器的順序來(lái)進(jìn)行上浮操作。
由于畫(huà)圖工具太繁瑣师痕，操作流程可以參考網(wǎng)上的一個(gè)示例：
圖片來(lái)源于：JDK源碼研究PriorityQueue（優(yōu)先隊(duì)列)
peek方法和poll方法
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];
// 取數(shù)組中最后一個(gè)元素的值
E x = (E) queue[s];
// 將堆中最后一個(gè)值設(shè)置為null
queue[s] = null;
// 如果數(shù)組不是只有一個(gè)元素，執(zhí)行下沉操作
if (s != 0)
// 下沉操作
siftDown(0, x);
return result;
}
??這兩個(gè)都是出隊(duì)的方法而账。其中胰坟，peek方法特別簡(jiǎn)單，就是取出堆中最小值元素，然后不移除數(shù)據(jù)笔横，不用調(diào)整堆竞滓。
??而poll方法是取出堆中最小值的同時(shí)，移除該數(shù)據(jù)吹缔，同樣商佑，為了保證最小堆的性質(zhì)，我們需要對(duì)堆進(jìn)行另一種操作：下沉（siftDown）厢塘。
siftDown方法
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
// 計(jì)算非葉子結(jié)點(diǎn)元素的最大位置茶没，循環(huán)的終止條件（在最后一個(gè)非葉子節(jié)點(diǎn)處結(jié)束）
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
// 計(jì)算k位置處的左子結(jié)點(diǎn)
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
// 右子結(jié)點(diǎn)等于左子結(jié)點(diǎn)下標(biāo)加1
int right = child + 1;
// 獲取左右孩子中值較小的值
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
// 然后重新和父結(jié)點(diǎn)進(jìn)行比較，如果大于父結(jié)點(diǎn)晚碾，不需要移動(dòng)抓半，結(jié)束
if (key.compareTo((E) c) <= 0)
break;
// 父結(jié)點(diǎn)下移
queue[k] = c;
// 改變下標(biāo)，循環(huán)此操作
k = child;
}
queue[k] = key;
}
- 先計(jì)算非葉子結(jié)點(diǎn)元素的最大位置格嘁；
- 循環(huán)判斷是否是葉子結(jié)點(diǎn)笛求；
- 計(jì)算根結(jié)點(diǎn)的左右子結(jié)點(diǎn)（也可以邏輯理解為將尾結(jié)點(diǎn)移動(dòng)至根結(jié)點(diǎn)位置），然后循環(huán)比較根結(jié)點(diǎn)的左右子結(jié)點(diǎn)與尾結(jié)點(diǎn)值大小糕簿，直到尾結(jié)點(diǎn)的值小于其左右結(jié)點(diǎn)探入，或者尾結(jié)點(diǎn)處于葉子結(jié)點(diǎn)位置上時(shí)循環(huán)終止。
由于siftDownUsingComparator方法內(nèi)部和siftDownComparable類似懂诗，就不解釋了蜂嗽。
??當(dāng)最小元素14出隊(duì)，從數(shù)組尾處取39賦值給隊(duì)首响禽。之后徒爹，進(jìn)行和增加元素后相反的動(dòng)作即下沉。
??首先選出根節(jié)點(diǎn)（父節(jié)點(diǎn)）39的兩個(gè)孩子結(jié)點(diǎn)中較小者芋类，和39交換位置隆嗅；當(dāng)39找到新位置后，執(zhí)行同種方法侯繁，如果孩子結(jié)點(diǎn)為null或者都比39大胖喳，則結(jié)束。
remove方法
public boolean remove(Object o) {
//獲取元素的下標(biāo)
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
/**
* 執(zhí)行移除操作
*/
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
// 如果要移除的就是最后一個(gè)元素贮竟，賦值為null
if (s == i) // removed last element
queue[i] = null;
else {
// 取隊(duì)列尾元素
E moved = (E) queue[s];
// 將隊(duì)尾元素置為null
queue[s] = null;
// 下沉操作
siftDown(i, moved);
// 如果下移后元素位置沒(méi)發(fā)生變化丽焊，說(shuō)明moved的左右子結(jié)點(diǎn)都大于moved，這時(shí)就需要上浮操作
if (queue[i] == moved) {
// 上浮操作
siftUp(i, moved);
// 如果上浮之后發(fā)生了元素位置
if (queue[i] != moved)
return moved;
}
}
return null;
}
通過(guò)代碼咕别，我們可以知道remove方法是從隊(duì)列中移除指定元素技健，如果該元素有不止一個(gè)，則移除數(shù)組中的一個(gè)出現(xiàn)的元素惰拱。
其他方法
/**
* 查看是否包含雌贱，只需要拿indexOf的返回值和1進(jìn)行比較即可
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* 獲取元素的下標(biāo)
*/
private int indexOf(Object o) {
if (o != null) {
// 循環(huán)遍歷
for (int i = 0; i < size; i++)
// 調(diào)用equals方法進(jìn)行比較
if (o.equals(queue[i]))
return i;
}
return -1;
}
到這里，大部分方法都基本上分析完了。
總結(jié)
- 優(yōu)先隊(duì)列是基于最小堆來(lái)實(shí)現(xiàn)的一種無(wú)界的隊(duì)列欣孤，所以馋没，隊(duì)頭出隊(duì)的元素總是最小的。該隊(duì)列不允許null元素降传，可以自定義優(yōu)先級(jí)篷朵，也就是比較規(guī)則；
- 該隊(duì)列不是線程安全的婆排，如果要在線程安全的場(chǎng)景下使用声旺，建議使用線程安全的PriorityBlockingQueue類；
本文參考自：
https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
JDK源碼研究PriorityQueue（優(yōu)先隊(duì)列）
