1、堆優(yōu)先隊列（Priority Queue）：特殊的“隊列”，取出元素的順序是 依照元素的優(yōu)先權（關鍵字）大小，而不是元素進入隊列的先后順序。問題：如何組織優(yōu)先隊列？一般的數(shù)組、鏈表？有序的數(shù)組或者鏈表？二叉搜索樹？ AVL樹？若采用數(shù)組或鏈表實現(xiàn)優(yōu)先隊列數(shù)組 : ( 1 ) ( n ) O( n ) 元素總是尾部刪除 查找最大（或最小）關鍵字從數(shù)組中刪去需要移動元素鏈表: ( 1 ) ( n ) ( 1 ) 元素總是鏈表的頭部刪除 查找最大（或最?。╆P鍵字刪去結點有序數(shù)組:O( n ) 或 O(log2 n )O( n ) ( 1 )找到合適的位置移動元素并刪去最后一個元素刪除 有序鏈表: O

2、( n ) ( 1 ) ( 1 )找到合適的位置元素刪除首元素或最后元素刪除 是否可以采用二叉樹結構？二叉搜索樹？如果采用二叉樹結構，應更關注樹結點順序怎么安排？樹結構怎樣？還是刪除？優(yōu)先隊列的完全二叉樹表示abcgdefih堆的兩個特性結構性：用數(shù)組表示的完全二叉樹；有序性：任一結點的關鍵字是其子樹所有結點的最大值(或最小值)“最大堆(MaxHeap)”,也稱“大頂堆”：最大值 “最小堆(MinHeap)”,也稱“小頂堆” ：最小值01234567891011abcdefghi【例】最大堆和最小堆303833【例】不是堆30注意：從根結點到任意結點路徑上結點序列的有序性！堆的抽象數(shù)據類型描述

3、類型名稱：最大堆（MaxHeap）數(shù)據對象集：完全二叉樹，每個結點的元素值不小于其子結點的元素值操作集：最大堆H MaxHeap，元素item ElementType，主要操作有：MaxHeap Create(MaxSize )：創(chuàng)建一個空的最大堆。IsFull( MaxHeap H )：判斷最大堆H是否已滿。Insert( MaxHeap H, ElementType item )：將元素item最大堆H。IsEmpty( MaxHeap H )：判斷最大堆H是否為空。ElementType DeleteMax( MaxHeap H )：返回H中最大元素(高優(yōu)先級)。最大堆的操作最大堆的創(chuàng)建

4、typedef struct HeapStructstruct HeapStruct 把MaxData換成 小于堆中所有元素的 MinData，同樣適用于創(chuàng)建最小堆。*MaxHeap;ElementType *Elements; /*/堆元素的Size; Capacity;/* 堆的當前元素個數(shù)/* 堆的最大容量;MaxHeap Create(MaxSize )/* 創(chuàng)建容量為MaxSize的空的最大堆 */MaxHeap H = malloc( sizeof( s ruct HeapStruct ) );H-Elements = malloc( (MaxSize+1) * sizeof(El

5、ementType); H-Size = 0;H-Capacity = MaxSize;H-Elements0 = MaxData;/* 定義“哨兵”為大于堆中所有可能元素的值，便于以后更快操作 */return H;最大堆的1 58232544316184105Case 1 :new_item = 2020313531584458 Elements0已經定義為哨兵 */i;if ( IsFull(H) ) prf(最大堆已滿); return;i = +H-Size; /* i指向后堆中的最后一個元素的位置 */for ( ; H-Elementsi/2 Elementsi = H-Elem

6、entsi/2; /* 向下過濾結點 */ H-Elementsi = item; /* 將item*/算法：將新增結點到從其父結點到根結點的有序序列中哨兵:100020T (N) = O ( log N )151286void Insert( MaxHeap H, ElementType item ) /* 將元素item最大堆H，其中H-Eleme為哨兵 */i;H-Element 0 是哨兵元素，if ( IsFull(H) ) 它不小于堆中的最大元素，prf(最大堆已滿);控制順環(huán)結束。return;i = +H-Size; /* i指向后堆中的最后一個元素的位置 */for ( ;

7、H-Elementsi/2 Elementsi = H-Elementsi/2; /* 向下過濾結點 */ H-Elementsi = item; /* 將item*/最大堆的刪除取出根結點（最大值）元素，同時刪除堆的一個結點。把 31 移至根441232535找出31的較大的孩子4425Elements1; /* 取出根結點最大值 */* 用最大堆中最后一個元素從根結點開始向上過濾下層結點temp = H-ElementsH-Size-;*/for( Parent=1; Parent*2Size; Parent=Child ) Child = Parent * 2;if( (Child!=

8、H-Size) &(H-ElementsChild ElementsChild+1)Child+; /* Child指向左右子結點的較大者 */if( temp = H-ElementsChild ) break;)/* 移動temp元素到下一層 */elseH-ElementsParent = H-ElementsChild;H-ElementsParent = temp;return MaxItem;最大堆的建立建立最大堆：將已經存在的N個元素按最大堆的要求存放在一個一維數(shù)組中方法1：通過操作，將N個元素一個個相繼到一個初始為空的堆中去，其時間代價最大為O(N logN)。方法2：性時間復雜度下建立最大堆。將N個元素按輸入順序存入，先滿足完全二叉樹的結構特性調整各結點位置，以滿足最大堆的有序特性。考慮結點當前考慮結點當前考慮結點794366837373202020873891955373702024499當前考慮結點當前考慮結點當前考慮結點779918798139873972484733866999554449333091線性時間復雜度T(n)=O(n)8783結點