1、算法設計與分析2007.91第五章 堆排序堆的基本概念和性質堆的基本操作（過程及分析）堆排序算法（過程及分析）堆排序應用優先級隊列（過程及分析）程序展示和講解2一、堆的基本概念和性質1、定義： 堆可看作為一完全二叉樹，大根堆的任一 非終端節點（葉子節點） 的數據不小于其子節點的數據。2、兩個特點： 根節點上為該堆的最大元素。 較大的數據位于較低的層次。3堆的屬性1、 lengthA：數組中的元素個數2、heapsizeA:存放在A中的堆的元素個數 顯然heapsizeA lengthA3、給定一個節點的下標i，其父節點為 i/2 ，其左兒子LEFT(i)為2i、右兒子 RIGHT(i)為2i+

2、1.4五個基本過程1、HEAPIFY過程:維持堆性質，運行時間O(lgn).2、BUILD-HEAP過程：從無序的輸入數組中構造出一個堆來，運行時間O(n). 3、HEAPSORT過程：對一個數組進行排序，運行時間O(nlgn). 4、EXTRACT-MAX和INSERT過程：是堆結構可以作為一個優先級隊列來用，運行時間O(lgn). 5堆實例6二、堆的基本操作HEAPIFY過程1、過程說明：對于第i個數，假定以它左兒子LEFT(i)和右兒子 RIGHT(i)為根的兩棵子樹都已為堆，調用HEAPIFY使得以i為根的子樹成為一個的堆。2、過程圖例783、算法如下1、lLEFT(i)2、rRIGH

3、T(i)3、if lheapsize(A)andAlAi4、 then largestl5、 else largesti6、if rheapsize(A) andArAlargest7、 then largestr8、if largesti9、 then exchange AiAlargest10、 HEAPIFY(A,largest)94、運行時間 T(n)=T(2/3n)+（1） 可得T(n)=O（lgn) 因為堆的高度最大為lgn 所以可知T(n)= O（lgn)10BUILD-HEAP過程1、圖例2、 BUILD-HEAP(A)算法 1) heapsizeAlengthA 2) for

4、 i lengthA/2 downto 1 3) do HEAPIFY(A,i)3、運行時間 111213粗估： 每調一次HEAPIFY(A,i)的時間為O（lgn)，總共有O（n)次調用，故運行時間最多為O（nlgn).此時間是不緊確的。緊確估計：含n個元素的堆中至多有 個節點的高度為h1415三、堆排序算法1、圖例：2、算法1) BUILDHEAP(A)2) for ilengthA downto 23) do exchange A1Ai4) heapsize(A)heapsize(A)-15) HEAPIFY(A,1)3、運行時間16171819堆排序的時間建堆的時間為O(n)+（n-1

5、)次的HEAPIFY調用時間 O(lgn)，所以總的代價為O(nlgn)20四、優先級隊列一、常見操作1、INSERT(S,x):把元素x插入集合S. 可記為SSx.2、MAXIMUM(S):返回S中具有最大關鍵字的元素。3、EXTRACTMAX(S):去掉并返回S中具有最大關鍵字的元素。21HEAP-EXTRACT-MAX過程HEAPEXTRACTMAX(A)if heapsize A1 and APARENT(i)key 4、 do AiAPARENT(i) 5、 iPARENT(i) 6、 Aikey3、運行時間： O(lgn)2425第五章 堆排序概念：二叉樹、完全二叉樹、根、葉節點、