《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件6-08堆排序1

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：丁慧 堆排序常州信息職業(yè)技術(shù)學(xué)院0203堆排序（1）定義：n個(gè)關(guān)鍵字序列kl,k2,kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下 性質(zhì)： kik2i且kik2i+1(1in/2) 或 kik2i且kik2i+1(1in/2)思考：若將此序列所存儲(chǔ)的向量R1.n看做是一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子結(jié)點(diǎn)的關(guān)鍵字。堆的任一子樹亦是堆。1、堆三、鏈表的插入04關(guān)鍵字序列(12,35,15,47,40,18,68,56)12153540186856475635124018476

2、815堆排序滿足堆的性質(zhì)，因此該序列是堆關(guān)鍵字序列(56,12,35,15, 40,18, 47,68)不滿足堆的性質(zhì)，因此不是堆05堆排序（2）大根堆和小根堆 根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆； 根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者的堆稱為大根堆。（3）堆的特點(diǎn) 大根堆（或小根堆）中，堆頂記錄的關(guān)鍵字最大（或最小），因此在堆中很容易選取最大（或最?。╆P(guān)鍵字的記錄。堆的樹形結(jié)構(gòu)記錄了大部分記錄關(guān)鍵字之間的大小關(guān)系，因此可減少記錄關(guān)鍵字的比較次數(shù)。06堆排序初始狀態(tài)：將R1.n構(gòu)造為初始堆；無(wú)序區(qū)包含所有記錄R1.n，有序區(qū)為空2、用大根

3、堆排序方法 交換：將錐頂記錄R1 和無(wú)序區(qū)的最后一個(gè)記錄Rn交換，由此得到新的無(wú)序區(qū)R1n-1和有序區(qū)Rn，且滿足R1n-1.keysRn.key重建堆:由于交換后新的錐頂記錄R1可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R1.n-1調(diào)整為堆。（1）第一趟排序：（2）第i趟排序：排序前狀態(tài)：無(wú)序區(qū)為R1.n-(i-1)，有序區(qū)為Rn-(i-1)+1.n，無(wú)序區(qū)在第i-1趟已調(diào)整為堆 交換：將堆頂記錄R1與無(wú)序區(qū)的最后一個(gè)記錄Rn-i+1交換，得到新的無(wú)序區(qū)R1n-i和有序區(qū)Rn-i+1.n重建堆:由于交換后新的錐頂記錄R1可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R1.n-i調(diào)整為堆。（3）重復(fù)進(jìn)行第i趟的操作，直到無(wú)序區(qū)只有一個(gè)元素為止。07堆排序3、堆排序算法void HeapSort(SeqList R) /對(duì)R1.n進(jìn)行堆排序，用R0做暫存單元int i;BuildHeap(R); /對(duì)R1.n構(gòu)建初始堆for(i=1;in;i+) /對(duì)當(dāng)前無(wú)序區(qū)R1. n-(i-1)進(jìn)行堆排序，共做n-1趟R0=R1; /將堆頂與當(dāng)前無(wú)序區(qū)最后一個(gè)記錄交換R1=Rn-(i-1