1 優(yōu)先隊列應用

隊列是一種先進先出的數(shù)據(jù)結構，先放入隊列的元素會先出隊列。但是有這樣一種場景，我們希望出隊列順序不是根據(jù)放入隊列順序，而是根據(jù)元素本身具有的優(yōu)先級，例如元素優(yōu)先級高則先出隊列，這時就要使用優(yōu)先隊列。

1.1 應用一

我們設想這樣一種發(fā)送消息的業(yè)務場景：消息具有優(yōu)先級屬性，在同一個隊列中優(yōu)先發(fā)送優(yōu)先級高的消息，優(yōu)先級定義如下：

//?優(yōu)先級?P1?>?P2?>?p3
public?enum?PriorityEnum?{

????P1(1,?"優(yōu)先級1"),

????P2(2,?"優(yōu)先級2"),

????P3(3,?"優(yōu)先級3")
????
????;
}

消息對象定義如下：

public?class?MyMessage?implements?Comparable?{

????/**
?????*?消息優(yōu)先級
?????*/
????private?int?priority;

????/**
?????*?消息內容
?????*/
????private?String?messge;

????public?MyMessage(int?priority,?String?message)?{
????????this.priority?=?priority;
????????this.messge?=?message;
????}

????@Override
????public?int?compareTo(Object?obj)?{
????????MyMessage?message?=?(MyMessage)?obj;
????????return?this.priority?-?message.priority;
????}
}

java.util.PriorityQueue可以實現(xiàn)上述功能：

public?class?PriorityQueueTest?{
????public?static?void?main(String[]?args)?{
????????PriorityQueue?messageQueue?=?new?PriorityQueue();
????????MyMessage?m1?=?new?MyMessage(PriorityEnum.P1.getCode(),?"message1");
????????MyMessage?m2?=?new?MyMessage(PriorityEnum.P2.getCode(),?"message2");
????????MyMessage?m3?=?new?MyMessage(PriorityEnum.P3.getCode(),?"message3");
????????messageQueue.offer(m3);
????????messageQueue.offer(m1);
????????messageQueue.offer(m2);
????????while?(messageQueue.size()?>?0)?{
????????????System.out.println(messageQueue.poll());
????????}
????}
}

代碼執(zhí)行結果：

send message=MyMessage(priority=1, messge=message1)
send message=MyMessage(priority=2, messge=message2)
send message=MyMessage(priority=3, messge=message3)

PriorityQueueTest消息放入優(yōu)先隊列順序：

3、1、2

PriorityQueueTest從優(yōu)先隊列獲取消息順序：

1、2、3

1.2 應用二

現(xiàn)在消息優(yōu)先級進行業(yè)務變更：

//?優(yōu)先級?P3?>?P2?>?p1
public?enum?PriorityEnum?{

????P1(1,?"優(yōu)先級1"),

????P2(2,?"優(yōu)先級2"),

????P3(3,?"優(yōu)先級3")
????
????;
}

此時預期輸出順序如下：

3、2、1

如果要達到預期輸出順序代碼要進行如下變更：

public?class?MyMessage?implements?Comparable?{

????@Override
????public?int?compareTo(Object?obj)?{
????????MyMessage?message?=?(MyMessage)?obj;
????????return?message.priority?-?this.priority;?//?比較關系變更
????}
}

2 二叉堆

在第一章節(jié)我們看到PriorityQueue可以實現(xiàn)按照元素優(yōu)先級順序進行輸出，那么其底層原理是什么呢？答案是二叉堆。

2.1 什么是二叉堆

二叉堆分為大頂堆和小頂堆，我們首先看大頂堆，從下圖可以看到整棵樹中最大值在根節(jié)點，所以稱為大頂堆：

我們再看小頂堆，從下圖可以看到整棵樹中最小值在根節(jié)點，所以稱為小頂堆：

2.2 怎么存儲二叉堆

二叉堆看似復雜，其實用數(shù)組就可以表示，我們以大頂堆為例：

第一步聲明一個長度為10的數(shù)組，因為二叉樹總共有10個節(jié)點：

int[] array = new int[10]

第二步設置根節(jié)點100作為數(shù)組第一個元素：

array[0] = 100

第三步設置所有節(jié)點至數(shù)組相應位置：

leftChildIndex = (parentIndex * 2) + 1
rightChildIndex = (parentIndex * 2) + 2

例如設置90至數(shù)組相應位置，其父節(jié)點100索引等于0，90是100左子節(jié)點：

parentIndex = 0
leftChildIndex = (0 * 2) + 1 = 1
array[1] = 90

例如設置80至數(shù)組相應位置，其父節(jié)點100索引等于0，80是100右子節(jié)點：

parentIndex = 0
leftChildIndex = (0 * 2) + 2 = 2
array[2] = 80

例如設置30至數(shù)組相應位置，其父節(jié)點80索引等于2，30是80右子節(jié)點：

parentIndex = 2
leftChildIndex = (2 * 2) + 2 = 6
array[6] = 30

第四步如果已知子節(jié)點數(shù)組索引，也可以反推出其父節(jié)點索引：

parentIndex = (childIndex - 1) / 2

例如已知節(jié)點30索引等于6，那么可以反推其父節(jié)點80索引等于2：

childIndex = 6
parentIndex = (6 - 1) / 2 = 2

2.3 新增元素

現(xiàn)在向二叉堆新增節(jié)點92，第一步在數(shù)組最后一個索引位置插入此元素：

這顯然不符合二叉堆的基本要求，需要循環(huán)與其父節(jié)點進行比較，如果發(fā)現(xiàn)大于父節(jié)點則交換位置，否則退出循環(huán)。第一輪比較92大于60，二者交換位置：

第二輪比較92大于90，二者交換位置：

第三輪比較92小于100，無需交換并退出循環(huán)：

最后一個節(jié)點92開始在最后，通過循環(huán)比較向上不斷移動至相應位置，這個過程被稱為SiftUp，可以理解為上浮。

2.4 獲取并刪除堆頂元素

整棵樹哪一個元素對業(yè)務最有價值？無疑是堆頂元素。以大頂堆為例，最大值永遠都在堆頂，可以理解為優(yōu)先級最高的元素永遠在堆頂，只要循環(huán)取出堆頂元素，那么可以達到按照優(yōu)先級順序進行處理目的。

當獲取到堆頂元素后需要移除此元素，這就可能涉及到二叉堆元素位置變化，下面演示這個過程，第一輪獲取堆頂元素100：

第二輪將最后一個元素60從原有位置刪除，并設置到堆頂位置：

第三輪比較60與左右子節(jié)點92和80，選取較大子節(jié)點92，92大于60，二者交換位置：

第四輪比較60與左右子節(jié)點40和90，選取較大子節(jié)點90，90大于60，二者交換位置：

第五輪比較60與左子節(jié)點50，50小于60，無需交換并退出循環(huán)：

最后一個節(jié)點60首先移動至根節(jié)點，再通過循環(huán)比較向下移動至相應位置，這個過程被稱為SiftDown，可以理解為下沉。

3 手寫大頂堆

經(jīng)過第二章節(jié)分析我們知道，二叉堆最重要方法是新增元素和獲取并刪除堆頂元素，其中最重要的是SiftUp和SiftDown兩個過程。

3.1 接口聲明

public?interface?IMaxHeap<E?extends?Comparable>?{

????/**
?????*?新增元素
?????*
?????*?@param?element?待新增元素
?????*?@return?true表示成功
?????*/
????public?boolean?offer(E?element);

????/**
?????*?獲取并刪除堆頂元素
?????*
?????*?@return?最大值
?????*/
????public?E?getAndRemoveTop();

????/**
?????*?堆大小
?????*
?????*?@return?堆大小
?????*/
????public?int?size();
}

3.2 大頂堆實現(xiàn)

public?class?MyMaxHeap<E?extends?Comparable>?implements?IMaxHeap<E>?{

????private?ArrayList?array;

????public?MyMaxHeap()?{
????????array?=?new?ArrayList();
????}

????@Override
????public?boolean?offer(E?element)?{
????????//?1.新增至數(shù)組最后
????????int?lastIndex?=?size();
????????array.add(lastIndex,?element);

????????//?2.ShfitUp
????????shiftUp(lastIndex);
????????return?Boolean.TRUE;
????}

????@Override
????public?E?getAndRemoveTop()?{
????????//?1.根節(jié)點為最大值
????????E?max?=?array.get(0);

????????//?2.最后節(jié)點移動至根節(jié)點并刪除
????????int?lastIndex?=?size()?-?1;
????????E?lastNode?=?array.get(lastIndex);
????????array.set(0,?lastNode);
????????array.remove(lastIndex);

????????//?3.ShiftDown
????????shiftDown(0);

????????//?4.返回最大值
????????return?max;
????}

????@Override
????public?int?size()?{
????????return?array.size();
????}

????//?節(jié)點上浮
????private?void?shiftUp(int?currentIndex)?{
????????//?根節(jié)點無需上浮
????????while?(currentIndex?!=?0)?{
????????????//?當前節(jié)點
????????????E?currentValue?=?array.get(currentIndex);
????????????//?父索引
????????????int?parentIndex?=?getParentIndex(currentIndex);
????????????//?父節(jié)點
????????????E?parentValue?=?array.get(parentIndex);
????????????//?當前節(jié)點小于父節(jié)點則退出循環(huán)
????????????if?(currentValue.compareTo(parentValue)?0)?{
????????????????break;
????????????}
????????????//?當前節(jié)點大于等于父節(jié)點則交換位置
????????????array.set(parentIndex,?currentValue);
????????????array.set(currentIndex,?parentValue);
????????????currentIndex?=?parentIndex;
????????}
????}

????//?節(jié)點下沉
????private?void?shiftDown(int?currentIndex)?{
????????//?當前節(jié)點沒有左子節(jié)點則不需要再下沉
????????while?(getLeftChildIndex(currentIndex)?????????????//?當前節(jié)點
????????????E?currentValue?=?array.get(currentIndex);
????????????//?左子索引
????????????int?leftChildIndex?=?getLeftChildIndex(currentIndex);
????????????//?左子節(jié)點
????????????E?leftChildValue?=?array.get(leftChildIndex);
????????????//?右子索引
????????????Integer?rightChildIndex?=?null;
????????????E?rightChildValue?=?null;
????????????if?(getRightChildIndex(currentIndex)?????????????????rightChildIndex?=?getRightChildIndex(currentIndex);
????????????????rightChildValue?=?array.get(rightChildIndex);
????????????}
????????????//?右子節(jié)點存在
????????????if?(null?!=?rightChildIndex)?{
????????????????//?找出左右子節(jié)點較大節(jié)點
????????????????int?biggerIndex?=?rightChildIndex;
????????????????if?(leftChildValue.compareTo(rightChildValue)?>?0)?{
????????????????????biggerIndex?=?leftChildIndex;
????????????????}
????????????????//?較大節(jié)點小于當前節(jié)點則退出循環(huán)
????????????????E?biggerValue?=?array.get(biggerIndex);
????????????????if?(biggerValue.compareTo(currentValue)?0)?{
????????????????????break;
????????????????}
????????????????//?較大節(jié)點大于等于當前節(jié)點則交換位置
????????????????array.set(currentIndex,?biggerValue);
????????????????array.set(biggerIndex,?currentValue);
????????????????currentIndex?=?biggerIndex;
????????????}
????????????//?右子節(jié)點不存在
????????????else?{
????????????????//?左子節(jié)點小于當前節(jié)點則退出循環(huán)
????????????????if?(leftChildValue.compareTo(currentValue)?0)?{
????????????????????break;
????????????????}
????????????????//?左子節(jié)點大于等于當前節(jié)點則交換位置
????????????????array.set(currentIndex,?leftChildValue);
????????????????array.set(leftChildIndex,?currentValue);
????????????????currentIndex?=?leftChildIndex;
????????????}
????????}
????}

????//?獲取左子節(jié)點索引
????private?int?getLeftChildIndex(int?currentIndex)?{
????????return?currentIndex?*?2?+?1;
????}

????//?獲取右子節(jié)點索引
????private?int?getRightChildIndex(int?currentIndex)?{
????????return?currentIndex?*?2?+?2;
????}

????//?獲取父節(jié)點索引
????private?int?getParentIndex(int?currentIndex)?{
????????if?(currentIndex?==?0)?{
????????????throw?new?RuntimeException("root?node?has?no?parent");
????????}
????????return?(currentIndex?-?1)?/?2;
????}

????public?ArrayList?getArray()?{
????????return?array;
????}

????public?void?setArray(ArrayList?array)?{
????????this.array?=?array;
????}
}

3.3 代碼測試

public?class?MyMaxHeapTest?{
????public?static?void?main(String[]?args)?{
????????MyMaxHeap?maxHeap?=?new?MyMaxHeap();
????????maxHeap.offer(70);
????????maxHeap.offer(90);
????????maxHeap.offer(80);
????????maxHeap.offer(100);
????????maxHeap.offer(60);
????????System.out.println("maxHeap?test?offer,?heapInfo="?+?maxHeap.getArray());
????????Integer?maxValue?=?maxHeap.getAndRemoveTop();
????????System.out.println("maxHeap?test?getAndRemoveTop,?maxValue="?+?maxValue?+?",?heapInfo="?+?maxHeap.getArray());
????}
}

代碼執(zhí)行結果：

maxHeap test offer, heapInfo=[100, 90, 80, 70, 60]
maxHeap test getAndRemoveTop, maxValue=100, heapInfo=[90, 70, 80, 60]

4 手寫優(yōu)先隊列

我們在第三章節(jié)手寫了大頂堆，那么手寫優(yōu)先隊列就很簡單了，只需要聲明一個隊列對大頂堆進行封裝，并提供隊列相關訪問方法即可。

4.1 接口聲明

public?interface?IPriorityQueue<E?extends?Comparable>?{

????/**
?????*?新增元素
?????*
?????*?@param?element?元素
?????*/
????public?void?offer(E?element);

????/**
?????*?獲取隊列首元素
?????*
?????*?@return?首元素
?????*/
????public?E?poll();

????/**
?????*?獲取隊列長度
?????*
?????*?@return?隊列長度
?????*/
????public?int?size();
}

4.2 優(yōu)先隊列實現(xiàn)

public?class?MyPriorityQueue<E?extends?Comparable>?implements?IPriorityQueue<E>?{

????private?MyMaxHeap?myMaxHeap;

????public?MyPriorityQueue()?{
????????myMaxHeap?=?new?MyMaxHeap();
????}

????@Override
????public?void?offer(E?element)?{
????????myMaxHeap.add(element);
????}

????@Override
????public?E?poll()?{
????????return?myMaxHeap.getAndRemoveTop();
????}

????@Override
????public?int?size()?{
????????return?myMaxHeap.size();
????}
}

4.3 代碼測試

public?class?PriorityQueueTest?{
????public?static?void?main(String[]?args)?{
????????MyPriorityQueue?myPriorityQueue?=?new?MyPriorityQueue();
????????myPriorityQueue.offer(10);
????????myPriorityQueue.offer(30);
????????myPriorityQueue.offer(20);
????????while?(myPriorityQueue.size()?>?0)?{
????????????System.out.println(myPriorityQueue.poll());
????????}
????}
}

代碼執(zhí)行結果：

30
20
10

5 源碼分析

5.1 PriorityQueue

我們看到在offer方法進行了siftUp，規(guī)則是當前節(jié)點小于父節(jié)點則交換位置，在poll方法進行了siftDown，規(guī)則是當前節(jié)點大于較大子節(jié)點則交換位置。

這兩個規(guī)則表示使用了小頂堆，可以解釋第一章節(jié)應用一輸出順序。在應用二修改對象比較規(guī)則，交換比較順序，那么可以實現(xiàn)大頂堆功能。

package?java.util;

public?class?PriorityQueue<E>?extends?AbstractQueue<E>?implements?java.io.Serializable?{

????private?static?final?int?DEFAULT_INITIAL_CAPACITY?=?11;

????transient?Object[]?queue;

????private?int?size?=?0;

????private?final?Comparatorsuper?E>?comparator;

????public?PriorityQueue()?{
????????this(DEFAULT_INITIAL_CAPACITY,?null);
????}

????public?PriorityQueue(Comparatorsuper?E>?comparator)?{
????????this(DEFAULT_INITIAL_CAPACITY,?comparator);
????}

????//?新增元素
????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;
????}

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

????private?void?siftUpComparable(int?k,?E?x)?{
????????Comparablesuper?E>?key?=?(Comparablesuper?E>)?x;
????????while?(k?>?0)?{
????????????//?父索引
????????????int?parent?=?(k?-?1)?>>>?1;
????????????//?父節(jié)點
????????????Object?e?=?queue[parent];
????????????//?當前節(jié)點大于等于父節(jié)點則退出循環(huán)
????????????if?(key.compareTo((E)?e)?>=?0)
????????????????break;
????????????//?當前節(jié)點小于父節(jié)點則交換位置上浮
????????????queue[k]?=?e;
????????????k?=?parent;
????????}
????????queue[k]?=?key;
????}

????//?獲取并刪除隊首元素
????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;
????}

????private?void?siftDown(int?k,?E?x)?{
????????if?(comparator?!=?null)
????????????siftDownUsingComparator(k,?x);
????????else
????????????siftDownComparable(k,?x);
????}

????private?void?siftDownComparable(int?k,?E?x)?{
????????Comparablesuper?E>?key?=?(Comparablesuper?E>)x;
????????int?half?=?size?>>>?1;
????????while?(k?????????????//?左子索引
????????????int?child?=?(k?<1)?+?1;
????????????//?左子節(jié)點
????????????Object?c?=?queue[child];
????????????//?右子索引
????????????int?right?=?child?+?1;
????????????//?比較左右子節(jié)點較大節(jié)點
????????????if?(right?super?E>)?c).compareTo((E)?queue[right])?>?0)
????????????????c?=?queue[child?=?right];
????????????//?當前節(jié)點小于等于較大節(jié)點則退出循環(huán)
????????????if?(key.compareTo((E)?c)?<=?0)
????????????????break;
????????????//?當前節(jié)點大于較大節(jié)點則交換位置下沉
????????????queue[k]?=?c;
????????????k?=?child;
????????}
????????queue[k]?=?key;
????}
}

5.2 DelayQueue

延時隊列底層使用優(yōu)先隊列，優(yōu)先級指標是元素本身時間屬性，在新增元素時越靠近隊列頭部，元素到期時間越早。

在取出堆頂元素時，首先調用元素getDelay方法，通常是元素時間減去當前時間，如果元素時間小于等于當前時間，表示元素已經(jīng)到期則取出并刪除隊首元素。

package?java.util.concurrent;

public?class?DelayQueue<E?extends?Delayed>?extends?AbstractQueue<E>?implements?BlockingQueue<E>?{

????private?final?transient?ReentrantLock?lock?=?new?ReentrantLock();
????private?final?PriorityQueue?q?=?new?PriorityQueue();

????public?boolean?offer(E?e)?{
????????final?ReentrantLock?lock?=?this.lock;
????????lock.lock();
????????try?{
????????????q.offer(e);
????????????if?(q.peek()?==?e)?{
????????????????leader?=?null;
????????????????available.signal();
????????????}
????????????return?true;
????????}?finally?{
????????????lock.unlock();
????????}
????}

????public?E?poll()?{
????????final?ReentrantLock?lock?=?this.lock;
????????lock.lock();
????????try?{
????????????//?獲取隊首元素
????????????E?first?=?q.peek();
????????????//?隊首元素時間大于當前時間表示沒到期
????????????if?(first?==?null?||?first.getDelay(NANOSECONDS)?>?0)
????????????????return?null;
????????????//?隊首元素時間小于等于當前時間表示到期則取出并刪除
????????????else
????????????????return?q.poll();
????????}?finally?{
????????????lock.unlock();
????????}
????}
}

6 文章總結

第一本文首先使用了java.util.PriorityQueue進行功能演示，從應用一可以看出其默認使用了小頂堆，從應用二可以看出當改變對象比較關系之后，可以達到大頂堆效果。

第二本文介紹了二叉堆相關概念，二叉堆分為大頂堆和小頂堆，其中最重要的兩個方法是新增元素和獲取并刪除堆頂元素，最重要的兩個過程是上浮和下沉。

第三本文手寫了大頂堆和優(yōu)先隊列，其中大頂堆最重要的是處理上浮和下沉這兩個過程，優(yōu)先隊列在大頂堆基礎上進行封裝。

第四本文分析了PriorityQueue與DelayQueue源碼，其中優(yōu)先隊列默認使用小頂堆，延時隊列底層使用優(yōu)先隊列，優(yōu)先級指標是時間，希望本文對大家有所幫助。