【數據結構和演算法：簡單方法】談一談優先隊列的實現
【系列文章推薦閱讀】
- 【數據結構之順序表】用圖和程式碼讓你搞懂順序結構線性表
- 【數據結構之鏈表】看完這篇文章我終於搞懂鏈表了
- 【數據結構之棧】用詳細圖文把「棧」搞明白（原理篇）
- 【數據結構之隊列】詳細圖解！在學習隊列？看這一篇就夠了！
- 【數據結構之鏈表】詳細圖文教你花樣玩鏈表
- 【數據結構之二叉樹】一文看懂二叉樹的概念和原理
- 【數據結構之二叉樹】二叉樹的創建及遍歷實現
- 【數據結構之線索二叉樹】線索二叉樹的原理及創建
- 【數據結構之二叉堆】二叉堆的原理及操作
首先回憶一下隊列（詳細內容移步至隊列詳解），只要記住八個字即可：先進先出（FIFO），後進後出（LILO）。
就像去醫院門診看病排隊時一樣：先來的先看，看完先走。
而優先隊列的特性正是「優先」二字，「優先」二字意味著打破了「常規」「規則」。
優先隊列不再遵守普通隊列的先進先出的原則了，如何不遵守呢？
- 最大優先隊列：不管入隊順序如何，誰的值最大誰先出隊
- 最小優先隊列：不管入隊順序如何，誰的值最小誰先出隊
比如，對於最大優先隊列，入隊順序為：14352，出隊順序則為：54321；對於最小優先隊列，入隊順序為：14352，出隊順序則為：12345.
舉個例子：醫院的急診病例，即便來的晚，也是可以優先看病的，因為生命至上。遇到災難危險時，群眾中會先疏散小孩子。
如果在諸如此類需要講「優先」的情況下，再去講什麼「先進先出」的排隊規則，那就不太好了。
那麼該如何實現優先隊列呢？
首先，在優先隊列中，想要出隊元素，肯定要先找到最大值，或者最小值；
其次，優先隊列「不講常規」，所以進隊順序已經不重要了，重要的是找到當前隊列中的最大值或最小值。
那麼，有沒有一個能直接找到最大值或最小值，並不在意其它順序的方法呢？
有！這個方法就是二叉堆！（詳細內容請移步至二叉堆詳解）
- 二叉堆的堆頂是該堆中的最大值或最小值
- 插入一個結點，即插入到二叉堆的最末尾，然後會再次調整構成二叉堆
- 刪除一個結點，即刪除堆頂，然後會再次調整構成二叉堆
所以可以藉助二叉堆來實現優先隊列，最大堆實現最大優先隊列，最小堆實現最小優先隊列
- 出隊即把堆頂出隊
- 入隊即向二叉堆中插入一個結點
- 出隊即刪除堆頂
天作之合！完美~
下面是最大優先隊列的程式碼實現。
優先隊列的結構體即是二叉堆的結構體：
typedef struct {
int array[MAXSIZE];
int length;
} BinaryHeap, PriorityQueue;
入隊操作：
/**
* @description: 最大優先隊列入隊
* @param {PriorityQueue} *queue 隊列指針
* @param {int} elem 入隊元素
* @return {*} 無
*/
void en_max_queue(PriorityQueue *queue, int elem)
{
insert_into_max_heap(queue, elem);
}
出隊操作：
/**
* @description: 最大優先隊列出隊
* @param {PriorityQueue} *queue 隊列指針
* @param {int} *elem 保存變數指針
* @return {*} 無
*/
void de_max_queue(PriorityQueue *queue, int *elem)
{
delete_from_max_heap(queue, elem);
}
函數 insert_into_max_heap、delete_from_max_heap 的實現在文章【二叉堆的原理及操作】中已經實現了，這裡不再贅述。
以上就是優先隊列的內容。
如有錯誤，還請指正。
如果覺得寫的不錯，可以點個贊和關注。後續會有更多數據結構和演算法相關文章。
