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

背景：處理有序元素時，不一定要求所有數(shù)據(jù)有序，只要求處理當(dāng)前最大（優(yōu)先級最高）的元素 優(yōu)先級隊列：支持 刪除最大元素 和 插入元素 兩種操作的一種數(shù)據(jù)結(jié)構(gòu)

【1】優(yōu)先級隊列的基本表現(xiàn)形式

優(yōu)先級隊列的基本實現(xiàn)可以使用 有序 或 無序 的 數(shù)組 和 鏈表

【2】基于二叉堆的優(yōu)先隊列實現(xiàn)方法

基于數(shù)組或鏈表的操作最壞情況下需線性時間完成，而用堆來實現(xiàn)優(yōu)先級隊列可以使兩種操作更快執(zhí)行

（1）基本定義

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

（2）二叉堆的相關(guān)算法

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

（3）優(yōu)先級隊列的實現(xiàn)

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

【3】堆排序

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

（1）堆的構(gòu)造

（2）下沉排序

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

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