思考：多個(gè)任務(wù)需要執(zhí)行，如何調(diào)整其執(zhí)行順序？
優(yōu)先隊(duì)列：特殊的“隊(duì)列”，取出元素的順序是依照元素的優(yōu)先權(quán)（關(guān)鍵字）大小，而不是元素進(jìn)入隊(duì)列的先后順序。

若采用數(shù)組或者鏈表實(shí)現(xiàn)優(yōu)先隊(duì)列：
數(shù)組：插入－元素總是插入尾部；刪除－查找最大（或最?。╆P(guān)鍵字 從數(shù)組中刪去需要移動(dòng)元素
鏈表：插入－元素總是插入鏈表的頭部；刪除－查找最大（或最小）關(guān)鍵字 刪去結(jié)點(diǎn)
有序數(shù)組：插入－找到合適位置 移動(dòng)元素并插入；刪除－刪去最后一個(gè)元素
有序鏈表：插入－找到合適位置 插入元素；刪除－刪去最后一個(gè)元素或首元素

是否可以采用二叉樹(shù)存儲(chǔ)結(jié)構(gòu)？
二叉搜索樹(shù)？不能簡(jiǎn)單地利用二叉搜索樹(shù)，輸入插入、刪除操作都比較簡(jiǎn)單，但當(dāng)我們每次都刪除最大值（即最右結(jié)點(diǎn)）會(huì)導(dǎo)致搜索樹(shù)變斜，高度不變 復(fù)雜度也不變
如果采用二叉樹(shù)結(jié)構(gòu)，應(yīng)該更加關(guān)注刪除；樹(shù)結(jié)點(diǎn)順序安排：根結(jié)點(diǎn)為最大值 每次刪除都刪除根結(jié)點(diǎn)，樹(shù)的結(jié)構(gòu)采用完全二叉樹(shù) 任何結(jié)點(diǎn)值都比左右子樹(shù)結(jié)點(diǎn)值大。

－堆的兩個(gè)特性：

結(jié)構(gòu)性：用數(shù)組表示的完全二叉樹(shù)
有序性：任一結(jié)點(diǎn)的關(guān)鍵字是其子樹(shù)所有結(jié)點(diǎn)的最大值（或最小值）
“最大堆（MaxHeap）”也稱“大頂堆”：最大值；“最小堆（MinHeap）”也稱“小頂堆”：最小值

－最大堆的主要操作：

－最大堆的創(chuàng)建：

typedef struct HeapStruct *MaxHeap ;
struct HeapStruct {
ElementType *Element ; // 存儲(chǔ)堆元素的數(shù)組
int Size; // 堆的當(dāng)前元素個(gè)數(shù)
int Capacity ; // 堆的最大容量
}

MaxHeap Create ( int MaxSize )
{ // 創(chuàng)建容量為MaxSize的空的最大堆
MaxHeap H = malloc ( sizeof ( struct HeapStruct ) ) ;
H -> Elements = malloc ( ( MaxSize + 1 ) * sizeof ( ElementType ) ) ;
// 下標(biāo)為1的位置開(kāi)始存值，下標(biāo)為0的位置不存放堆元素
H -> Size = 0 ;
H -> Capacity = MaxSize ;
H -> Element [0] = MaxData ; // 定義“哨兵”為大于堆中所有可能元素的值 便于以后更快操作
return H ;
}

－最大堆的插入：

void Insert ( MaxHeap H , ElementType item )
{ // 將元素item插入最大堆H，其中H -> Elements [0] 已經(jīng)定義為哨兵
int i ;
if ( IsFull ( H ) ) {
printf ( “最大堆已滿” ) ;
return ;
}
i = ++H -> Size ; // i 指向插入后堆中的最后一個(gè)元素的位置
for ( ; H -> Elements [ i/2 ] < item; i /= 2 ) // 與父結(jié)點(diǎn)做比較，i / 2 表示的就是父結(jié)點(diǎn)的下標(biāo)
H -> Element [ i ] = H -> Elements [ i/2 ]; // 向下過(guò)濾結(jié)點(diǎn)
H -> Elements [ i ] = item ; // 將 item 插入
}
H -> Element [ 0 ]是哨兵元素，它不小于堆中的最大元素 控制循環(huán)結(jié)束（哨兵比所有值都大 所以當(dāng)插入的新元素比較大要放入下標(biāo)為1位置時(shí)就直接與哨兵比較 循環(huán)結(jié)束新元素插入樹(shù)的最頂層；若沒(méi)有哨兵 則需要對(duì) i 判斷 當(dāng) i == 1時(shí)就可知道插入的新元素是最大值）

－最大堆的刪除：

取出根結(jié)點(diǎn)（最大值）元素，同時(shí)刪除堆的一個(gè)結(jié)點(diǎn)
步驟：1.將根結(jié)點(diǎn)刪除，2.把位置最后那個(gè)結(jié)點(diǎn)移至根結(jié)點(diǎn)位置 即下標(biāo)為1的位置，3.找出此時(shí)根結(jié)點(diǎn)中較大的孩子 并使其與根結(jié)點(diǎn)交換位置 重復(fù)該步驟直到最后
ElementType DeleteMax ( MaxHeap H )
{ // 從最大堆H中取出鍵值為最大的元素 并刪除一個(gè)結(jié)點(diǎn)
int Parent, Child ;
ElementType MaxItem , temp ;
if ( IsEmpty ( H ) ) {
printf ( “最大堆以為空” ) ;
return;
}
MaxItem = H -> Elements [ 1 ] ; // 取出根結(jié)點(diǎn)最大值
// 用最大堆中最后一個(gè)元素從根結(jié)點(diǎn)開(kāi)始向上過(guò)濾下層結(jié)點(diǎn)
temp = H -> Elements [ H -> Size — ] ;
for ( Parent = 1; Parent * 2 <= H -> Size ; Parent = Child ){
Child = Parent * 2 ;
if ( ( Child != H -> Size ) && ( H -> Elements [Child] < H -> Elements [Child + 1] ) )
Child ++; // Child指向左右結(jié)點(diǎn)的較大者
if ( temp >= H -> Elements [ Child ] ) break ;
else // 移動(dòng)temp元素到下一層
H -> Elements [ Parent ] = H -> Elements [ Child ] ;
}
H -> Elements [ Parent ] = temp ;
return MaxItem ;
}

－最大堆的建立：

堆的一個(gè)應(yīng)用是：堆排序，需要先建堆
建立最大堆：將已經(jīng)存在的N個(gè)元素按最大堆的要求存放在一個(gè)一維數(shù)組中
方法1：通過(guò)插入操作，將N個(gè)元素一個(gè)個(gè)相繼插入到一個(gè)初始為空的堆中去，其時(shí)間代價(jià)最大為 O( N logN )。
方法2：在線性時(shí)間復(fù)雜度下建立最大堆。
（1）將N個(gè)元素按輸入順序存入，先滿足完全二叉樹(shù)的結(jié)構(gòu)特性
（2）調(diào)整各結(jié)點(diǎn)位置，以滿足最大堆的有序特性
倒數(shù)第一個(gè)有兒子的結(jié)點(diǎn)開(kāi)始 逐漸將它們調(diào)整成堆（調(diào)整：將結(jié)點(diǎn)與其左右兒子中比較大的兒子交換位置 直到結(jié)點(diǎn)比它左右兒子都大為止）