文章收錄在首發公衆号：bigsai 期待你的到訪！
前言
事情還要從一個故事講起：
對于上面那隻可愛的小狗狗不會，本篇即為該教程，首先，我要告訴這隻可愛的小狗狗，這種問題你要使用的資料結構為優先隊列，每次操作的時間複雜度為
O(logn)
,而整個過程的時間複雜度為
O(nlogn)
.
對于本片的設計與實作和堆排序可能有些相似，因為他們都借助堆來實作算法和資料結構，下面詳細介紹優先隊列的設計與實作。
堆
而堆就是一類特殊的資料結構的統稱。堆通常是一個可以被看做一棵樹(完全)的數組對象。且總是滿足以下規則：
- 堆總是一棵完全二叉樹
- 每個節點總是大于(或小于)它的孩子節點。
對于完全二叉樹，我想大家都能明白，就是最底層葉子節點要嚴格按照從左向右來。
堆有大根堆和小根堆，如果是所有父節點都大于子節點的時候，那麼這就是個大根堆，反之則為小根堆，以下就是一個大根堆：
最後需要注意的是我們并不是用鍊式去儲存這個二叉樹而是用數組去存儲這個樹，雖然鍊式的使用場景可能更多一些，但是在完全二叉樹的情況下空間使用率較好沒有斜樹的出現。并且在操作的時候可以直接通過編号找到位置進行交換。
優先隊列
如何了解優先隊列，我們先從一段對話說起：
優先隊列，它是一個隊列。而普通的隊列遵從先進先出的規則。而優先隊列遵循一個排序的規則：每次抛出自定義排序最大(小)的，預設的情況是抛出最小的，本篇也就從最基本的原理進行分析。
并且它的用法隊列還是一樣的，，是以我們在設計這個類的時候api方面要與隊列的api一緻。
我們主要實作add、poll、和peek方法，并且會着重于算法的實作而不太着重一些細節的實作。
雖然優先隊列和堆排序利用堆結構特性的流程有一些相似，但是兩者其實還是有些操作上的差別的：
堆排序 ：
- 剛開始是一個雜亂無章的序列，是以需要将雜亂的序列（樹）通過一個方法變成一個合法的堆。
- 轉成一個堆之後需要删除n次每次删除完都要重新調整這個堆。沒有插入操作。
優先隊列：
- 隊列（堆）剛開始的内容為空，每次增加一個元素時需要即使調整堆。每次删除也要及時調整堆，增加和删除每次都隻是一個元素。
但是優先隊列的具體操作流程是如何的呢？我們具體分析其插入和删除的流程。
插入add流程(小根堆為例)：
- 正常處理完的優先隊列内的資料滿足一個堆的結構，是以就是插入在堆中。
- 堆是一棵完全二叉樹，是以在插入初始，插入到最後一個位置不影響其他結構。
- 節點和父節點比較大小(父節點索引為其二分之一)。如果該節點比父節點更小，則交換資料，一直到不能交換為止，這個過程不用擔心不合法，因為父節點更小的話更滿足比孩子節點更小。
删除pop流程(小根堆為例)：
- pop删除操作取優先隊列内最小的元素，而這個元素肯定就是堆頂元素了，取完之後，這個堆的其他部分還是滿足堆的結構但是缺少堆頂。
- 為了不影響整個結構，我們将末尾的那個元素移到堆頂，此時堆需要調整使其滿足堆的性質條件。
- 交換的這個節點和左右孩子進行比較，如果需要交換則交換，交換後再次考慮交換子節點是否需要交換，一直到不交換為止。最壞情況是交換到根節點，這個複雜度每次為O(logn).
代碼實作
我想到這裡，優先隊列的内部流程思想你已經掌握了，但是懂優先隊列原理和手寫優先隊列是兩個概念，為了更深入的學習優先隊列，在這裡就帶你手寫一個簡易型的優先隊列。
在代碼的具體實作方面，最主要的就是pop()和add()兩個函數了。在pop()函數具體實作的時候，将最後一個元素移到堆頭考慮和其他孩子節點交換的時候，用while進行操作的時候計算孩子下标的時候要確定不越界。我們用的是數組存儲資料，優先隊列的長度不一定等于這個數組的長度。
而在實作add()函數的時候，這裡簡單的考慮了一下擴容。
具體實作的代碼為：
import java.util.Arrays;
public class priQueue {
private int size;//優先隊列的大小
private int capacity;//數組的容量
private int value[];//儲存的值
public priQueue() {
this.capacity = 10;
this.value = new int[capacity];
this.size=0;
}
public priQueue(int capacity) {
this.capacity = capacity;
this.value = new int[capacity];
this.size=0;
}
/**
* 插入元素
* @param number
*/
public void add(int number) {
if(size==capacity)//擴容
{
capacity*=1.5;
value= Arrays.copyOf(value,capacity);
}
value[size++]=number;//先加到末尾
int index=size-1;
while (index>=1) {//進行交換
if(value[index]<value[index/2]) {
swap(index,index/2,value);
index=index/2;
}
else//不需要交換即停止
break;
}
}
public int peek() {
return value[0];
}
/**
* 抛出隊頭
* @return
*/
public int pop() {
int val=value[0];//呆傳回資料額
value[0]=value[--size];//将最後一個元素指派在堆頭
int index=0,leftChild=0,rightChild=0;
while (true)
{
leftChild=index*2+1;
rightChild=index*2+2;
if(leftChild>=size)//左孩子必須滿足在條件内
break;
else if(rightChild<size&&value[rightChild]<value[index]&&value[rightChild]<value[leftChild])
{//右孩子更小
swap(index,rightChild,value);
index=rightChild;
}
else if(value[leftChild]<value[index])
{//左孩子更小
swap(index,leftChild,value);
index=leftChild;
}
else //不需要 它自己最小
break;
}
return val;
}
//交換兩個元素
public void swap(int i,int j,int arr[]) {
int team=arr[i];
arr[i]=arr[j];
arr[j]=team;
}
public int size() {
return size;
}
} 寫個類測試一下看看：
結語
本次優先隊列介紹就到這裡啦，感覺不錯記得點贊或一鍵三連哦，建議和堆排序一起看和學習效果更佳，要能夠手寫代碼。個人公衆号：
bigsai
回複 bigsai 更多精彩和資源與你分享。