排序 - 選擇排序 - 堆排序（一）

　　堆排序

　　 堆排序定義

　　n個關鍵字序列K l K …K n 稱為堆當且僅當該序列滿足如下性質(簡稱為堆性質)

　　() k i ≤K i 且k i ≤K i+ 或()K i ≥K i 且k i ≥K i+ (≤i≤

)

　　若將此序列所存儲的向量R[n]看做是一棵完全二叉樹的存儲結構則堆實質上是滿足如下性質的完全二叉樹樹中任一非葉

　　結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字

　　【例】關鍵字序列()和()分別滿足堆性質()和()故它們均是堆其對應的

　　完全二叉樹分別如小根堆示例和大根堆示例所示

　　

　　大根堆和小根堆

　　根結點(亦稱為堆頂)的關鍵字是堆裡所有結點關鍵字中最小者的堆稱為小根堆

　　根結點(亦稱為堆頂)的關鍵字是堆裡所有結點關鍵字中最大者稱為大根堆

　　注意

　　①堆中任一子樹亦是堆

　　②以上討論的堆實際上是二叉堆(Binary Heap)類似地可定義k叉堆

　　堆排序特點

　　堆排序(HeapSort)是一樹形選擇排序

　　堆排序的特點是在排序過程中將R[ln]看成是一棵完全二叉樹的順序存儲結構利用完全二叉樹中雙親結點和孩子結點之

　　間的內在關系【參見二叉樹的順序存儲結構】在當前無序區中選擇關鍵字最大(或最小)的記錄

　　堆排序與直接插入排序的區別

　　直接選擇排序中為了從R[n]中選出關鍵字最小的記錄必須進行n次比較然後在R[n]中選出關鍵字最小的記錄又

　　需要做n次比較事實上後面的n次比較中有許多比較可能在前面的n次比較中已經做過但由於前一趟排序時未保留這些

　　比較結果所以後一趟排序時又重復執行了這些比較操作

　　堆排序可通過樹形結構保存部分比較結果可減少比較次數

From:http://tw.wingwit.com/Article/program/sjjg/201311/23781.html