原來實作優先級隊列如此簡單

假如你設計的事件系統中有很多的事件，每個事件都定義了不同的權重值，系統需要優先處理權重較高的事件，這裡你就需要使用到優先級隊列，本篇我們一起來學習實作優先級隊列的常用方式

在實作之前，首先我們需要先定義出優先級隊的API，優先級隊列是一種抽象的資料結構，我們依然可以基于前面我們使用到的隊列API來修改；需要了解之前的隊列的實作可以檢視《面試的季節到了，老哥确定不來複習下資料結構嗎》

其中的入隊列enqueue和出隊列dequeue是我們主要需要實作的方式，也是優先級隊列的核心方法

實作優先級隊列的最簡單實作可以參考《面試的季節到了，老哥确定不來複習下資料結構嗎》中棧的實作方式，enqueue和棧的push方式實作方式一緻，dequeue可以參考選擇排序的實作，循環一遍數組，找出最大值和數組最後一個元素交換，然後删除它；

這裡隻實作了定長的優先級隊列，如何實作自動擴容呢？也可以參考這篇文章《面試的季節到了，老哥确定不來複習下資料結構嗎》；基于無序數組實作的enqueue時間複雜度是O(1)，dequeue時間複雜度是O(n)

基于有序數組實作就是在入隊的時候保證數組有序，那麼在出隊列的時候可以直接删掉最大值；插入的過程和插入排序類似的操作

enqueue時間複雜度是O(n)，dequeue時間複雜度是O(1)

基于連結清單的實作與上面的類似，有興趣的可以自己實作

在《面試的季節到了，老哥确定不來複習下資料結構嗎》中我們實作的棧和隊列的操作都能夠在常數時間内完成，但是優先級隊列從上面的實作過程，我們發現初級版本的實作插入或删除最大值的操作最糟糕的情況會是線性時間。

在二叉堆中，每個節點都将大于等于它的子節點，也成為堆有序；其中根節點是最大的節點。

二叉堆的表示：

重點：

在一個二叉堆中，位置k節點的父節點的位置為k/2,它的兩個子節點的位置為2k和2k+1; 基于這點，我們可以用數組來表示二叉堆，通過移動數組的下标來找到節點父節點和子節點

在元素進行插入和删除操作的過程中，會破壞堆有序，是以我們需要做一些操作來保證堆再次有序；主要有兩種情況，當某個節點的優先級上升，我們需要由下向上恢複堆有序（下沉）；當某個節點優先級下降，我們需要由上向下恢複堆有序（上浮）

根據目前的節點k找到父節點的位置k/2，比較目前節點和父節點，如果比父節點大就交換，直到找個比目前節點大的父節點或者已上浮到了根節點

入隊操作：将新的元素添加到數組末尾，讓新元素上浮到适合位置，增加堆的大小

出隊操作：将最大的根節點删除，然後把最後一個元素放入到頂端，下層頂端元素到合适位置，減小堆大小

注意： 由于我們為了友善計算父節點和子節點的索引位置，是以數組中的第一個位置是不會使用的；可以自己思考下使用第一個位置，那麼子節點和父節點的位置應該如何計算？ 基于堆的實作，入隊和出隊的時間複雜對都是logN，解決了初級版本實作的問題。 數組大小動态擴容和縮容依然可以參考之前棧的實作方式