《數據結構（C語言描述）（第2版）》教學課件6-08堆排序1_第1頁
《數據結構（C語言描述）（第2版）》教學課件6-08堆排序1_第2頁
《數據結構（C語言描述）（第2版）》教學課件6-08堆排序1_第3頁
《數據結構（C語言描述）（第2版）》教學課件6-08堆排序1_第4頁
《數據結構（C語言描述）（第2版）》教學課件6-08堆排序1_第5頁
已閱讀5頁，還剩3頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論