1.堆
堆實際上是一棵完全二叉樹，其任何一非葉節點滿足性質：
key[i]<=key[2i+1]&&key[i]<=key[2i+2]或者key[i]>=key[2i+1]&&key>=key[2i+2]
即任何一非葉節點的關鍵字不大于或者不小于其左右孩子節點的關鍵字。
堆分為大頂堆和小頂堆，滿足key[i]>=key[2i+1]&&key>=key[2i+2]稱為大頂堆，滿足 key[i]<=key[2i+1]&&key[i]<=key[2i+2]稱為小頂堆。由上述性質可知大頂堆的堆頂的關鍵字肯定是所有關鍵字中最大的，小頂堆的堆頂的關鍵字是所有關鍵字中最小的。
2.堆排序的思想
利用大頂堆(小頂堆)堆頂記錄的是最大關鍵字(最小關鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。
其基本思想為(大頂堆)：
1)将初始待排序關鍵字序列(r1,r2....rn)建構成大頂堆，此堆為初始的無序區；
2)将堆頂元素r[1]與最後一個元素r[n]交換，此時得到新的無序區(r1,r2,......rn-1)和新的有序區(rn),且滿足r[1,2...n-1]<=r[n];
3)由于交換後新的堆頂r[1]可能違反堆的性質，是以需要對目前無序區(r1,r2,......rn-1)調整為新堆，然後再次将r[1]與無序區最後一個元素交換，得到 新的無序區(r1,r2....rn-2)和新的有序區(rn-1,rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。
3.操作過程如下：
1)初始化堆：将r[1..n]構造為堆；
2)将目前無序區的堆頂元素r[1]同該區間的最後一個記錄交換，然後将新的無序區調整為新的堆。
是以對于堆排序，最重要的兩個操作就是構造初始堆和調整堆，其實構造初始堆事實上也是調整堆的過程，隻不過構造初始堆是對所有的非葉節點都進行調整。
4.舉例說明堆排序的操作過程
a首先是講一個無序的序列建構成一個個堆：
b.然後是輸出堆頂元素之後，調整剩餘元素成為一個新的堆：
5.下面是代碼部分：