一、基礎知識
我們通常所說的堆是指二叉堆，二叉堆又稱完全二叉樹或者叫近似完全二叉樹。二叉堆又分為最大堆和最小堆。
堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。數組可以根據索引直接獲取元素，時間複雜度為O（1），也就是常量，因此對於取值效率極高。
最大堆的特性如下：
最小堆的特性如下：
二、算法思想
1.最大堆的算法思想是：
先將初始的R[0…n-1]建立成最大堆，此時是無序堆，而堆頂是最大元素再將堆頂R[0]和無序區的最後一個記錄R[n-1]交換，由此得到新的無序區R[0…n-2]和有序區R[n-1]，且滿足R[0…n-2].keys ≤ R[n-1].key
由於交換後，前R[0…n-2]可能不滿足最大堆的性質，因此再調整前R[0…n-2]為最大堆，直到只有R[0]最後一個元素才調整完成。
最大堆排序完成後，其實是升序序列，每次調整堆都是要得到最大的一個元素，然後與當前堆的最後一個元素交換，因此最後所得到的序列是升序序列。
2.最小堆的算法思想是：
先將初始的R[0…n-1]建立成最小堆，此時是無序堆，而堆頂元素是最小的元素再將堆頂R[0]與無序區的最後一個R[n-1]交換，由此得到新的無序堆R[0…n-2]和有序堆R[n-1]，且滿足R[0…n-2].keys >= R[n-1].key
由於交換後，前R[0…n-2]可能不滿足最小堆的性質，因此再調整前R[0…n-2]為最小堆，直到只有R[0]最後一個元素才調整完成最小堆排序完成後，其實是降序序列，每次調整堆都是要得到最小的一個元素，然後與當前無序堆的最後一個元素交換，所以所得到的序列是降序的。
提示：堆排序的過程，其實就是不斷地擴大有序區，然後不斷地縮小無序區，直到只有有序區的過程。
三、排序過程分析
因為算法比較抽象，這裡直接通過舉個小例子來說明堆排序的過程是如何的。下面我們用這個無序序列採用最大堆的進行堆排序，所得到的序列就是升序序列（ASC）。
無序序列：89,-7,999,-89,7,0,-888,7,-7
第一步：初始化建成最大堆：
第二步：將堆頂最大元素999與無序區的最後一個元素交換，使999成為有序區。交換後，-7成為堆頂，由於-7並不是無序區中最大的元素，因此需要調整無序區，使無序區中最大值89成為堆頂，所以-7與89交換。交換後導致89的右子樹不滿足最大堆的性質，因此要對右子樹調整成最大堆，所以-7要與0交換，如下圖：
從圖中看到，當-7成89交換後，堆頂是最大元素了，但是-7的左孩子是0，右孩子是-888，由於-7<0，導致-7這個結點不滿足堆的性質，因此需要調整它。所以，0與-7交換。
然後不斷重複著第二步的過程，直到全部成為有序區。
最後：所得到的是升序序列
四、時間複雜度
堆排序的時間，主要由建立初始堆和反複調整堆這兩部分的時間開銷構成.由於堆排序是不穩定的，它得扭到的時間複雜度會根據實際情況較大，因此只能取平均時間複雜度。
平均時間複雜度為：O( N * log2(N) )
堆排序耗時的操作有：初始堆+ 反複調整堆，時間複雜度如下：
1.初始建堆：每個父節點會和左右子節點進行最多2次比較和1次交換，所以復雜度跟父節點個數有關。根據2x <= n（x為n個元素可以折半的次數，也就是父節點個數），得出x = log2n。即O ( log2n )
2.反複調整堆：由於初始化堆過程中，會記錄數組比較結果，所以堆排序對原序列的數組順序並不敏感，最好情況和最壞情況差不多。需要抽取n-1 次堆頂元素，每次取堆頂元素都需要重建堆（O(重建堆) < O(初始堆)）。所以小於O(n-1) * O(log2n)
使用建議：
由於初始化堆需要比較的次數較多，因此，堆排序比較適合於數據量非常大的場合（百萬數據或更多）。由於高效的快速排序是基於遞歸實現的，所以在數據量非常大時會發生堆棧溢出錯誤。
五、Java示例代碼
public class HeapSort{ private static int[] sort=new int[]{1,0,10,20,3,5,6,4,9,8,12, 17,34,11}; public static void main(String[] args){ buildMaxHeapify(sort); heapSort(sort); print(sort); } private static void buildMaxHeapify(int[] data){//沒有子節點的才需要創建最大堆，從最後一個的父節點開始int startIndex=getParentIndex(data.length-1);//從尾端開始創建最大堆，每次都是正確的堆for(int i=startIndex;i>=0;i--){ maxHeapify(data,data.length,i); } } /** *創建最大堆* *@paramdata *@paramheapSize需要創建最大堆的大小，一般在sort的時候用到，因為最多值放在末尾，末尾就不再歸入最大堆了*@paramindex當前需要創建最大堆的位置*/ private static void maxHeapify(int[] data,int heapSize,int index){//當前點與左右子節點比較int left=getChildLeftIndex(index); int right=getChildRightIndex(index); int largest=index; if(left<heapSize&&data[index]<data[left]){ largest=left; } if(right<heapSize&&data[largest]<data[right]){ largest=right; }//得到最大值後可能需要交換，如果交換了，其子節點可能就不是最大堆了，需要重新調整if(largest!=index){ int temp=data[index]; data[index]=data[largest]; data[largest]=temp; maxHeapify(data,heapSize,largest); } } /** *排序，最大值放在末尾，data雖然是最大堆，在排序後就成了遞增的* *@paramdata */ private static void heapSort(int[] data){//末尾與頭交換，交換後調整最大堆for(int i=data.length-1;i>0;i--){ int temp=data[0]; data[0]=data[i]; data[i]=temp; maxHeapify(data,i,0); } } /** *父節點位置* *@paramcurrent *@return */ private static int getParentIndex(int current){ return(current-1)>>1; } /** *左子節點position注意括號，加法優先級更高* *@paramcurrent *@return */ private static int getChildLeftIndex(int current){ return(current<<1)+1; } /** *右子節點position * *@paramcurrent *@return */ private static int getChildRightIndex(int current){ return(current<<1)+2; } private static void print(int[] data){ int pre=-2; for(int i=0;i<data.length;i++){ if(pre<(int)getLog(i+1)){ pre=(int)getLog(i+1); System.out.println(); } System.out.print(data[i]+"|"); } } /** *以2為底的對數* *@paramparam *@return */ private static double getLog(double param){ return Math.log(param)/Math.log(2); }}