本篇文章主要基于算法algorithm第四版

背景：處理有序元素時，不一定要求所有數據有序，只要求處理當前最大（優先級最高）的元素 優先級隊列：支持 刪除最大元素 和 插入元素 兩種操作的一種數據結構

【1】優先級隊列的基本表現形式

優先級隊列的基本實現可以使用 有序 或 無序 的 數組 和 鏈表

【2】基于二叉堆的優先隊列實現方法

基于數組或鏈表的操作最壞情況下需線性時間完成，而用堆來實現優先級隊列可以使兩種操作更快執行

（1）基本定義

因為二叉堆是完全二叉樹，所以只用數組就可以表示，在二叉堆中位置為k的父結點的位置為ceil（k/2），而子結點為2k和2k+1，這樣方便的表示也使其能通過數組索引方便地上下移動元素

（2）二叉堆的相關算法

在插入或刪除堆中元素時，會打破堆的狀態，所有需要對堆進行遍歷來恢復堆的狀態（堆有序 以及 完全二叉樹），這個過程稱為堆的有序化。有序化過程主要分為兩類：

（3）優先級隊列的實現

通過有序化的兩個過程我們便可實現插入元素以及刪除最大元素的操作 插入元素：將新元素加到數組末尾，增加堆的大小并讓這個新元素 上浮 到合適的位置 刪除最大元素：從數組刪去最大的元素并將最后一個元素放到堆頂，減小堆的大小，并讓該元素 下沉 到合適的位置

【3】堆排序

優先隊列可以變成一種排序方法，將所有元素插入一個查找最小元素 的優先隊列，然后再重復調用刪除最小元素的操作來將他們按順序刪去。以此方法來實現排序。 在進行堆排序時，首先要將一組無序數據建立起堆，然后再重復刪去最大（或小）元素

（1）堆的構造

（2）下沉排序

這一階段完成排序工作。從堆中刪除最大元素，然后放入堆縮小后數組中空出的位置，將堆尾元素放到堆頂，進行下沉操作。以此方法重復，則一個最大堆可以得到一個升序序列。

本人學識尚淺，有什么不對的歡迎指出，一起交流交流^ ^