面試官再問(wèn)你優(yōu)先級(jí)隊(duì)列，請(qǐng)把這篇文章丟給他
?程序員常用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin
完全開(kāi)源的淘客項(xiàng)目：https://github.com/silently9527/mall-coupons-server
微信公眾號(hào)：貝塔學(xué)Java
?
前言
假如你設(shè)計(jì)的事件系統(tǒng)中有很多的事件，每個(gè)事件都定義了不同的權(quán)重值，系統(tǒng)需要優(yōu)先處理權(quán)重較高的事件，這里你就需要使用到優(yōu)先級(jí)隊(duì)列，本篇我們一起來(lái)學(xué)習(xí)實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的常用方式
隊(duì)列API定義
在實(shí)現(xiàn)之前，首先我們需要先定義出優(yōu)先級(jí)隊(duì)的API，優(yōu)先級(jí)隊(duì)列是一種抽象的數(shù)據(jù)結(jié)構(gòu)，我們依然可以基于前面我們使用到的隊(duì)列API來(lái)修改；需要了解之前的隊(duì)列的實(shí)現(xiàn)可以查看《面試的季節(jié)到了，老哥確定不來(lái)復(fù)習(xí)下數(shù)據(jù)結(jié)構(gòu)嗎》
public interface Queue<T> extends Iterable<T> {
void enqueue(T item); //入隊(duì)列
T dequeue(); //出隊(duì)列
int size();
boolean isEmpty();
}
其中的入隊(duì)列enqueue和出隊(duì)列dequeue是我們主要需要實(shí)現(xiàn)的方式，也是優(yōu)先級(jí)隊(duì)列的核心方法
初級(jí)版本的實(shí)現(xiàn)
隊(duì)列API的抽象類
public abstract class AbstractQueue<T> implements Queue<T> {
private Comparator<T> comparator;
public AbstractQueue(Comparator<T> comparator) {
this.comparator = comparator;
}
public boolean less(T a, T b) {
return comparator.compare(a, b) < 0;
}
public void exch(T[] array, int i, int j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
基于無(wú)序數(shù)組實(shí)現(xiàn)
實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的最簡(jiǎn)單實(shí)現(xiàn)可以參考《面試的季節(jié)到了，老哥確定不來(lái)復(fù)習(xí)下數(shù)據(jù)結(jié)構(gòu)嗎》中棧的實(shí)現(xiàn)方式，enqueue和棧的push方式實(shí)現(xiàn)方式一致，dequeue可以參考選擇排序的實(shí)現(xiàn)，循環(huán)一遍數(shù)組，找出最大值和數(shù)組最后一個(gè)元素交換，然后刪除它；
public class DisorderPriorityQueue<T> extends AbstractQueue<T> {
private T[] queue;
private int size;
public DisorderPriorityQueue(int max, Comparator<T> comparator) {
super(comparator);
this.queue = (T[]) new Object[max];
}
@Override
public void enqueue(T item) {
queue[size++] = item;
}
@Override
public T dequeue() {
int index = 0;
for (int i = 1; i < size; i++) {
if (less(queue[index], queue[i])) {
index = i;
}
}
size--;
exch(queue, index, size);
T data = queue[size];
queue[size] = null;
return data;
}
//省略其他函數(shù)
}
這里只實(shí)現(xiàn)了定長(zhǎng)的優(yōu)先級(jí)隊(duì)列，如何實(shí)現(xiàn)自動(dòng)擴(kuò)容呢？也可以參考這篇文章《面試的季節(jié)到了，老哥確定不來(lái)復(fù)習(xí)下數(shù)據(jù)結(jié)構(gòu)嗎》；基于無(wú)序數(shù)組實(shí)現(xiàn)的enqueue時(shí)間復(fù)雜度是O(1)，dequeue時(shí)間復(fù)雜度是O(n)
基于有序數(shù)組實(shí)現(xiàn)
基于有序數(shù)組實(shí)現(xiàn)就是在入隊(duì)的時(shí)候保證數(shù)組有序，那么在出隊(duì)列的時(shí)候可以直接刪掉最大值；插入的過(guò)程和插入排序類似的操作
public class OrderPriorityQueue<T> extends AbstractQueue<T> {
private T[] queue;
private int size;
public OrderPriorityQueue(int max, Comparator<T> comparator) {
super(comparator);
this.queue = (T[]) new Object[max];
}
@Override
public void enqueue(T item) {
queue[size++] = item;
for (int i = size - 1; i > 1 && less(queue[i], queue[i - 1]); i--) {
exch(queue, i, i - 1);
}
}
@Override
public T dequeue() {
size--;
T data = queue[size];
queue[size] = null;
return data;
}
//省略其他函數(shù)
}
enqueue時(shí)間復(fù)雜度是O(n)，dequeue時(shí)間復(fù)雜度是O(1)
基于鏈表實(shí)現(xiàn)
基于鏈表的實(shí)現(xiàn)與上面的類似，有興趣的可以自己實(shí)現(xiàn)
?在《面試的季節(jié)到了，老哥確定不來(lái)復(fù)習(xí)下數(shù)據(jù)結(jié)構(gòu)嗎》中我們實(shí)現(xiàn)的棧和隊(duì)列的操作都能夠在常數(shù)時(shí)間內(nèi)完成，但是優(yōu)先級(jí)隊(duì)列從上面的實(shí)現(xiàn)過(guò)程，我們發(fā)現(xiàn)初級(jí)版本的實(shí)現(xiàn)插入或刪除最大值的操作最糟糕的情況會(huì)是線性時(shí)間。
?
二叉堆實(shí)現(xiàn)
二叉堆的定義
在二叉堆中，每個(gè)節(jié)點(diǎn)都將大于等于它的子節(jié)點(diǎn)，也成為堆有序；其中根節(jié)點(diǎn)是最大的節(jié)點(diǎn)。
二叉堆的表示：
重點(diǎn)：在一個(gè)二叉堆中，位置k節(jié)點(diǎn)的父節(jié)點(diǎn)的位置為k/2,它的兩個(gè)子節(jié)點(diǎn)的位置為2k和2k+1; 基于這點(diǎn)，我們可以用數(shù)組來(lái)表示二叉堆，通過(guò)移動(dòng)數(shù)組的下標(biāo)來(lái)找到節(jié)點(diǎn)父節(jié)點(diǎn)和子節(jié)點(diǎn)
在元素進(jìn)行插入和刪除操作的過(guò)程中，會(huì)破壞堆有序，所以我們需要做一些操作來(lái)保證堆再次有序；主要有兩種情況，當(dāng)某個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)上升，我們需要「由下向上恢復(fù)堆有序（下沉）」；當(dāng)某個(gè)節(jié)點(diǎn)優(yōu)先級(jí)下降，我們需要「由上向下恢復(fù)堆有序（上?。?/strong>
由上向下恢復(fù)堆有序（上浮）
private void swim(int k) {
while (k > 0 && less(queue[k / 2], queue[k])) {
exch(queue, k / 2, k);
k = k / 2;
}
}
根據(jù)當(dāng)前的節(jié)點(diǎn)k找到父節(jié)點(diǎn)的位置k/2，比較當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)，如果比父節(jié)點(diǎn)大就交換，直到找個(gè)比當(dāng)前節(jié)點(diǎn)大的父節(jié)點(diǎn)或者已上浮到了根節(jié)點(diǎn)
由下向上恢復(fù)堆有序（下沉）
private void sink(int k) {
while (2 * k <= size) {
int i = 2 * k;
if (less(queue[i], queue[i + 1])) {
i++;
}
if (less(queue[i], queue[k])) {
break;
}
exch(queue, i, k);
k = i;
}
}
二叉堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列
入隊(duì)操作：將新的元素添加到數(shù)組末尾，讓新元素上浮到適合位置，增加堆的大小 出隊(duì)操作：將最大的根節(jié)點(diǎn)刪除，然后把最后一個(gè)元素放入到頂端，下層頂端元素到合適位置，減小堆大小
public class BinaryHeapPriorityQueue<T> extends AbstractQueue<T> {
private T[] queue;
private int size;
public BinaryHeapPriorityQueue(int max, Comparator<T> comparator) {
super(comparator);
this.queue = (T[]) new Object[max + 1];
}
@Override
public void enqueue(T item) {
this.queue[++size] = item;
this.swim(size);
}
@Override
public T dequeue() {
T max = this.queue[1];
exch(this.queue, 1, size--);
this.queue[size + 1] = null; //釋放內(nèi)存
this.sink(1);
return max;
}
//省略其他函數(shù)
}
?注意：
由于我們?yōu)榱朔奖阌?jì)算父節(jié)點(diǎn)和子節(jié)點(diǎn)的索引位置，所以數(shù)組中的第一個(gè)位置是不會(huì)使用的；可以自己思考下使用第一個(gè)位置，那么子節(jié)點(diǎn)和父節(jié)點(diǎn)的位置應(yīng)該如何計(jì)算？
基于堆的實(shí)現(xiàn)，入隊(duì)和出隊(duì)的時(shí)間復(fù)雜對(duì)都是logN，解決了初級(jí)版本實(shí)現(xiàn)的問(wèn)題。
數(shù)組大小動(dòng)態(tài)擴(kuò)容和縮容依然可以參考之前棧的實(shí)現(xiàn)方式
?
文中所有源碼已放入到了github倉(cāng)庫(kù)https://github.com/silently9527/JavaCore
最后（點(diǎn)關(guān)注，不迷路）
文中或許會(huì)存在或多或少的不足、錯(cuò)誤之處，有建議或者意見(jiàn)也非常歡迎大家在評(píng)論交流。
最后，「寫(xiě)作不易，請(qǐng)不要白嫖我喲」，希望朋友們可以「點(diǎn)贊評(píng)論關(guān)注」三連，因?yàn)檫@些就是我分享的全部動(dòng)力來(lái)源??