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

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

【1】?jī)?yōu)先級(jí)隊(duì)列的基本表現(xiàn)形式

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

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

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

（1）基本定義

因?yàn)槎娑咽峭耆鏄?shù)，所以只用數(shù)組就可以表示，在二叉堆中位置為k的父結(jié)點(diǎn)的位置為ceil（k/2），而子結(jié)點(diǎn)為2k和2k+1，這樣方便的表示也使其能通過(guò)數(shù)組索引方便地上下移動(dòng)元素

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

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

（3）優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)

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

【3】堆排序

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

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

（2）下沉排序

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

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