Java集合—PriorityQueue底层原理
原文作者：漢尼博
原文地址：PriorityQueue的用法和底層實(shí)現(xiàn)原理
目錄
先講使用，再講原理
實(shí)現(xiàn)原理
方法剖析
先講使用，再講原理
隊(duì)列是遵循先進(jìn)先出（First-In-First-Out）模式的，但有時(shí)需要在隊(duì)列中基于優(yōu)先級(jí)處理對(duì)象。舉兩個(gè)例子：作業(yè)系統(tǒng)中的調(diào)度程序，當(dāng)一個(gè)作業(yè)完成后，需要在所有等待調(diào)度的作業(yè)中選擇一個(gè)優(yōu)先級(jí)最高的作業(yè)來(lái)執(zhí)行，并且也可以添加一個(gè)新的作業(yè)到作業(yè)的優(yōu)先隊(duì)列中；每日交易時(shí)段生成股票報(bào)告的應(yīng)用程序中，需要處理大量數(shù)據(jù)并且花費(fèi)很多處理時(shí)間。客戶(hù)向這個(gè)應(yīng)用程序發(fā)送請(qǐng)求時(shí)，實(shí)際上就進(jìn)入了隊(duì)列。我們需要首先處理優(yōu)先客戶(hù)再處理普通用戶(hù)。在這種情況下，Java的PriorityQueue(優(yōu)先隊(duì)列)會(huì)很有幫助。PriorityQueue類(lèi)在Java1.5中引入并作為?Java?Collections?Framework?的一部分。PriorityQueue是基于優(yōu)先堆的一個(gè)無(wú)界隊(duì)列，這個(gè)優(yōu)先隊(duì)列中的元素可以默認(rèn)自然排序或者通過(guò)提供的Comparator（比較器）在隊(duì)列實(shí)例化的時(shí)排序。
- 優(yōu)先隊(duì)列不允許空值，而且不支持non-comparable（不可比較）的對(duì)象，比如用戶(hù)自定義的類(lèi)。優(yōu)先隊(duì)列要求使用Java?Comparable和Comparator接口給對(duì)象排序，并且在排序時(shí)會(huì)按照優(yōu)先級(jí)處理其中的元素。優(yōu)先隊(duì)列的頭是基于自然排序或者Comparator排序的最小元素。如果有多個(gè)對(duì)象擁有同樣的排序，那么就可能隨機(jī)地取其中任意一個(gè)。當(dāng)我們獲取隊(duì)列時(shí)，返回隊(duì)列的頭對(duì)象。
- 優(yōu)先隊(duì)列的大小是不受限制的，但在創(chuàng)建時(shí)可以指定初始大小。當(dāng)我們向優(yōu)先隊(duì)列增加元素的時(shí)候，隊(duì)列大小會(huì)自動(dòng)增加。
- PriorityQueue是非線程安全的，所以Java提供了PriorityBlockingQueue（實(shí)現(xiàn)BlockingQueue接口）用于Java多線程環(huán)境。
我們有一個(gè)用戶(hù)類(lèi)Customer，它沒(méi)有提供任何類(lèi)型的排序。當(dāng)我們用它建立優(yōu)先隊(duì)列時(shí)，應(yīng)該為其提供一個(gè)比較器對(duì)象。
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隨機(jī)數(shù)生成隨機(jī)用戶(hù)對(duì)象。對(duì)于自然排序，我們使用Integer對(duì)象，這也是一個(gè)封裝過(guò)的Java對(duì)象。下面是最終的測(cè)試代碼，展示如何使用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) {//優(yōu)先隊(duì)列自然排序示例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);}//優(yōu)先隊(duì)列使用示例Queue<Customer> customerPriorityQueue =?new?PriorityQueue<>(7, idComparator);addDataToQueue(customerPriorityQueue);pollDataFromQueue(customerPriorityQueue);}//匿名Comparator實(shí)現(xiàn)public?static?Comparator<Customer> idComparator =?new?Comparator<Customer>(){@Overridepublic?int?compare(Customer c1, Customer c2) {return?(int) (c1.getId() - c2.getId());}};//用于往隊(duì)列增加數(shù)據(jù)的通用方法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));}}//用于從隊(duì)列取數(shù)據(jù)的通用方法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());}}}注意我用實(shí)現(xiàn)了Comparator接口的Java匿名類(lèi)，并且實(shí)現(xiàn)了基于id的比較器。當(dāng)我運(yùn)行以上測(cè)試程序時(shí)，我得到以下輸出：
Processing Integer:9 Processing Integer:16 Processing Integer:18 Processing Integer:25 Processing Integer:33 Processing Integer:75 Processing Integer:77 Processing Customer with ID=6 Processing Customer with ID=20 Processing Customer with ID=24 Processing Customer with ID=28 Processing Customer with ID=29 Processing Customer with ID=82 Processing Customer with ID=96從輸出結(jié)果可以清楚的看到，最小的元素在隊(duì)列的頭部因而最先被取出。如果不實(shí)現(xiàn)Comparator，在建立customerPriorityQueue時(shí)會(huì)拋出ClassCastException。
Exception?in?thread?"main"?java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparableat 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)實(shí)現(xiàn)原理
Java中PriorityQueue通過(guò)二叉小頂堆實(shí)現(xiàn)，可以用一棵完全二叉樹(shù)表示（任意一個(gè)非葉子節(jié)點(diǎn)的權(quán)值，都不大于其左右子節(jié)點(diǎn)的權(quán)值），也就意味著可以通過(guò)數(shù)組來(lái)作為PriorityQueue的底層實(shí)現(xiàn)。
上圖中我們給每個(gè)元素按照層序遍歷的方式進(jìn)行了編號(hào)，如果你足夠細(xì)心，會(huì)發(fā)現(xiàn)父節(jié)點(diǎn)和子節(jié)點(diǎn)的編號(hào)是有聯(lián)系的，更確切的說(shuō)父子節(jié)點(diǎn)的編號(hào)之間有如下關(guān)系：
leftNo = parentNo*2+1rightNo = parentNo*2+2parentNo = (nodeNo-1)/2通過(guò)上述三個(gè)公式，可以輕易計(jì)算出某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)以及子節(jié)點(diǎn)的下標(biāo)。這也就是為什么可以直接用數(shù)組來(lái)存儲(chǔ)堆的原因。PriorityQueue的peek()和element()操作是常數(shù)時(shí)間，add()、?offer()、poll()以及無(wú)參數(shù)的remove()方法的時(shí)間復(fù)雜度都是log(N)。
| add(E e) | offer(E e) | ? |
| element() | peek() | ? |
| remove() | poll() | ? |
| ? | ? | ? |
| ? | ? | ? |
| ? | ? | ? |
方法剖析
1. offer()：向優(yōu)先隊(duì)列中插入元素
新加入的元素可能會(huì)破壞小頂堆的性質(zhì)，因此需要進(jìn)行必要的調(diào)整。
//offer(E e) public boolean offer(E e) {if (e == null)//不允許放入null元素throw new NullPointerException();modCount++;int i = size;if (i >= queue.length)grow(i + 1);//自動(dòng)擴(kuò)容size = i + 1;if (i == 0)//隊(duì)列原來(lái)為空，這是插入的第一個(gè)元素queue[0] = e;elsesiftUp(i, e);//調(diào)整return true; }上述代碼中，擴(kuò)容函數(shù)grow()類(lèi)似于ArrayList里的grow()函數(shù)，就是再申請(qǐng)一個(gè)更大的數(shù)組，并將原數(shù)組的元素復(fù)制過(guò)去，這里不再贅述。需要注意的是siftUp(int k, E x)方法，該方法用于插入元素x并維持堆的特性。
//siftUp() private void siftUp(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)//調(diào)用比較器的比較方法break;queue[k] = e;k = parent;}queue[k] = x; }新加入的元素x可能會(huì)破壞小頂堆的性質(zhì)，因此需要進(jìn)行調(diào)整。調(diào)整的過(guò)程為：從k指定的位置開(kāi)始，將x逐層與當(dāng)前點(diǎn)的parent進(jìn)行比較并交換，直到滿(mǎn)足x >= queue[parent]為止。注意這里的比較可以是元素的自然順序，也可以是依靠比較器的順序。
2. peek()：獲取但不刪除隊(duì)首元素，也就是隊(duì)列中權(quán)值最小的那個(gè)元素。根據(jù)小頂堆的性質(zhì)，堆頂那個(gè)元素就是全局最小的那個(gè)；由于堆用數(shù)組表示，根據(jù)下標(biāo)關(guān)系，0下標(biāo)處的那個(gè)元素既是堆頂元素。所以直接返回?cái)?shù)組0下標(biāo)處的那個(gè)元素即可。
代碼也就非常簡(jiǎn)潔：
//peek() public E peek() {if (size == 0)return null;return (E) queue[0];//0下標(biāo)處的那個(gè)元素就是最小的那個(gè) }3.poll()：獲取并刪除隊(duì)首元素，由于刪除操作會(huì)改變隊(duì)列的結(jié)構(gòu)，為維護(hù)小頂堆的性質(zhì)，需要進(jìn)行必要的調(diào)整。
代碼如下：
上述代碼首先記錄0下標(biāo)處的元素，并用最后一個(gè)元素替換0下標(biāo)位置的元素，之后調(diào)用siftDown()方法對(duì)堆進(jìn)行調(diào)整，最后返回原來(lái)0下標(biāo)處的那個(gè)元素（也就是最小的那個(gè)元素）。重點(diǎn)是siftDown(int k, E x)方法，該方法的作用是從k指定的位置開(kāi)始，將x逐層向下與當(dāng)前點(diǎn)的左右孩子中較小的那個(gè)交換，直到x小于或等于左右孩子中的任何一個(gè)為止。
//siftDown() private void siftDown(int k, E x) {int half = size >>> 1;while (k < half) {//首先找到左右孩子中較小的那個(gè)，記錄到c里，并用child記錄其下標(biāo)int child = (k << 1) + 1;//leftNo = parentNo*2+1Object c = queue[child];int right = child + 1;if (right < size &&comparator.compare((E) c, (E) queue[right]) > 0)c = queue[child = right];if (comparator.compare(x, (E) c) <= 0)break;queue[k] = c;//然后用c取代原來(lái)的值k = child;}queue[k] = x; }4. remove(Object o)
remove(Object o)方法用于刪除隊(duì)列中跟o相等的某一個(gè)元素（如果有多個(gè)相等，只刪除一個(gè)），該方法不是Queue接口內(nèi)的方法，而是Collection接口的方法。由于刪除操作會(huì)改變隊(duì)列結(jié)構(gòu)，所以要進(jìn)行調(diào)整；又由于刪除元素的位置可能是任意的，所以調(diào)整過(guò)程比其它函數(shù)稍加繁瑣。具體來(lái)說(shuō)，remove(Object o)可以分為2種情況：1. 刪除的是最后一個(gè)元素。直接刪除即可，不需要調(diào)整。2. 刪除的不是最后一個(gè)元素，從刪除點(diǎn)開(kāi)始以最后一個(gè)元素為參照調(diào)用一次siftDown()即可。此處不再贅述。
具體代碼如下：
//remove(Object o) public boolean remove(Object o) {//通過(guò)遍歷數(shù)組的方式找到第一個(gè)滿(mǎn)足o.equals(queue[i])元素的下標(biāo)int i = indexOf(o);if (i == -1)return false;int s = --size;if (s == i) //情況1queue[i] = null;else {E moved = (E) queue[s];queue[s] = null;siftDown(i, moved);//情況2......}return true; }參考文獻(xiàn)：
https://www.cnblogs.com/CarpenterLee/p/5488070.html
http://www.importnew.com/6932.html
總結(jié)
以上是生活随笔為你收集整理的Java集合—PriorityQueue底层原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
