一.堆介紹
堆，是一棵完全二叉樹，根的值大于左右子樹中所有結點的值，左右子樹也是堆，除此之外，對其它元素之間的大小關系（如左右子樹之間元素大小關系）沒有要求。
這是大根堆，如果把“大于”換成“小于“，就是小根堆，這裡都以大根堆為例。
由于堆是完全二叉樹，是以可以用數組來模拟，在資料結構上算是比較簡單。
用數組模拟二叉樹（當然也包括堆）的話，如果根節點的下标為0的話，則對于每個結點i，其左孩子下标為2*i+1；其右孩子下标為2*i+2。
堆有兩個基本操作：插入元素和删除元素。
插入： 将待插入元素添加到數組末尾，然後依次向上比較，如果該結點大于父親節點，就與父節點交換，這樣就構成局部大根堆，一直到該結點小于父節點位置，便完成了結點的插入操作。
删除： 要删除某元素，可以将數組的大小縮小一，然後用數組的末尾元素代替待删除元素，然後将縮小後的數組重新調整為堆，便完成了結點的删除操作。
二.堆排序的思想
将待排序區分為無序區和有序區，無序區在前，有序區在後。未排序前無序區為整個待排序區間，沒有有序區。
排序的過程是，不斷地将無序區構造成一個大根堆，這樣無序區中的最大元素便被放置在了數組的最前面即根的位置，然後将無序區的第一個元素與最後一個元素交換，此動作将無序區的長度縮小一，将有序區的長度擴大一，即有序區前進一，無序區向前退一。然後将新的無序區（由于根節點的變化，此時很可能已經不是大根堆）重新調整為大根堆，等待下一次的交換。如此往複，不斷地将無序區的最大元素添加到有序區的前面，同時縮小無序區，直到有序區占滿待排序區為止。
這樣，還剩下兩個問題： 1.如何将一個交換後的無序區調整為大根堆； 2.如何在排序之前建立那個初始的大根堆。
而第二個問題是可以通過第一個問題的解決而解決的。這個稍後再談，現在先看第一個問題。
三.将一個交換後的無序區調整為大根堆(自堆頂至葉子)
由于進行元素交換前，無序區是一個大根堆，即左子樹和右子樹都是大根堆，是以根節點變化後左右子樹仍然都是大根堆，無序區裡的最大元素一定在新根節點、左右子樹的根節點這三個結點裡。先存儲新的根節點的值以待後用。如果新的根結點最大，說明已經是大根堆，調整完畢；否則比較左右子樹根節點，找出較大的，它是無序區現存的最大元素，應該作為新的大根堆中的根，是以将此節點上調至根節點位置，接下來就隻需要調整此結點原來所在的子樹為大根堆即可（因為大根堆對左右子樹之間元素的大小關系沒有要求！）。
這是一個疊代的過程，當某一個需要調整的子樹調整前就已經是大根堆（待調整的根節點比左右子樹根節點都大）時，或者下标已經超出無序區範圍時，疊代過程結束，無序區已經調整為大根堆。
這就是調整一個左右子樹都為大根堆的完全二叉樹為大根堆的過程。
首先，建立初始的堆結構如圖：
然後，交換堆頂的元素和最後一個元素，此時最後一個位置作為有序區（有序區顯示為黃色），然後進行其他無序區的堆調整，重新得到大頂堆後，交換堆頂和倒數第二個元素的位置……
重複此過程：
最後，有序區擴充完成即排序完成：
四.建立初始大根堆
若數組下标範圍為0~n，考慮到單獨一個元素是大根堆，則從下标[n/2]開始的元素均為大根堆。于是隻要從[n/2]-1開始，向前依次構造大根堆，這樣就能保證，構造到某個節點時，它的左右子樹都已經是大根堆（這就可以調用我們上面讨論的調整為大根堆的方法了）。一直到下标為0的結點，就完成了初始大根堆的建立。
堆排序用到的函數有兩個：1個将左右子樹都為大根堆的完全二叉樹調整為大根堆的調整函數；1個反複調用此調整函數來進行排序的排序函數。
本質上，堆排序就是選擇排序，每次選擇目前無序區最大的放入有序區。
對于直接選擇排序，選擇的過程要進行周遊，一次選擇過程的複雜度為o(n)。堆排序利用堆的性質和二叉樹的結構使得每次選擇的複雜度降低為o(logn)，進而有效地改進了選擇排序。
參考博文
<a href="http://blog.csdn.net/super_chris/article/details/4581900/" target="_blank">http://blog.csdn.net/super_chris/article/details/4581900/</a>
<a href="http://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html" target="_blank">http://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html</a>