本篇文章主要基于算法algorithm第四版
背景：處理有序元素時，不一定要求所有數據有序，只要求處理當前最大（優先級最高）的元素 優先級隊列：支持 刪除最大元素 和 插入元素 兩種操作的一種數據結構
優先級隊列的基本實現可以使用 有序 或 無序 的 數組 和 鏈表
無序數組或鏈表：刪除最大元素時需要將數組遍歷一遍造出最大元素，插入則無需額外操作有序數組或鏈表：刪除元素時只需直接刪除第一個，插入元素需要保持數據的有序（類似于插入排序） 特點：這類實現的插入元素或刪除最大元素在最壞情況下需要線性時間來完成基于數組或鏈表的操作最壞情況下需線性時間完成，而用堆來實現優先級隊列可以使兩種操作更快執行
因為二叉堆是完全二叉樹，所以只用數組就可以表示，在二叉堆中位置為k的父結點的位置為ceil（k/2），而子結點為2k和2k+1，這樣方便的表示也使其能通過數組索引方便地上下移動元素
在插入或刪除堆中元素時，會打破堆的狀態，所有需要對堆進行遍歷來恢復堆的狀態（堆有序 以及 完全二叉樹），這個過程稱為堆的有序化。有序化過程主要分為兩類：
某個結點的優先級上升（或是在堆底加入新元素時），需要由下至上恢復堆的順序，且形象地稱之為上浮某結點優先級下降（如將根節點替換為更小的元素時），需要由上至下恢復堆的順序，稱之為下沉通過有序化的兩個過程我們便可實現插入元素以及刪除最大元素的操作 插入元素：將新元素加到數組末尾，增加堆的大小并讓這個新元素 上浮 到合適的位置 刪除最大元素：從數組刪去最大的元素并將最后一個元素放到堆頂，減小堆的大小，并讓該元素 下沉 到合適的位置 
優先隊列可以變成一種排序方法，將所有元素插入一個查找最小元素 的優先隊列，然后再重復調用刪除最小元素的操作來將他們按順序刪去。以此方法來實現排序。 在進行堆排序時，首先要將一組無序數據建立起堆，然后再重復刪去最大（或?。┰?/p>
這一階段完成排序工作。從堆中刪除最大元素，然后放入堆縮小后數組中空出的位置，將堆尾元素放到堆頂，進行下沉操作。以此方法重復，則一個最大堆可以得到一個升序序列。
本人學識尚淺，有什么不對的歡迎指出，一起交流交流^ ^
新聞熱點
疑難解答
