堆排序的算法分析
堆排序算法分析
什么是堆
我們這里討論的堆是一種數據結構，而不是垃圾收集存儲機制。（二叉）堆一個數組，它可以被看成一個近似的完全二叉樹，即一棵樹上的每一個結點對應數組中的某一個元素，除了最底層外，該樹是完全填滿的，而且是從左往右填充。堆具有三個重要的屬性，即父結點、左孩子、右孩子。堆又分為兩種，即最大堆和最小堆，最大堆是指所有的父結點都要大于子結點，故根結點的“值”最大（這里堆中存儲的不一定是數值，可以是任何一種對象，只要實現了相應的equals()方法即可，下文中將以簡單的int數值類型為例來討論和編程）；而最小堆就相反，因而根結點最小。它們的性質可以用下面兩個數學表達式來表示：
最大堆性質：A[PARENT(i)]>=A[i]
最小堆性質：A[PARENT(i)]<=A[i]
（注意：這里的i是除了根結點以外的所有結點）
如果把堆看成一棵樹，可以定義一個堆中的結點的高度就是結點到葉結點最長簡單路徑上邊的個數，因而可以把堆的高度定義為根結點的高度。故此，我們可以得到：
一個具有n個元素的堆的高度為logn；
高度為h的堆中，元素個數最多為2^(h+1)-1個，元素個數最少為2^h個。
因此，我們可以聯想到，最大堆通過將根元素提取到結尾幾乎可以對應到降序排列，而最小堆通過將根元素提取到結尾幾乎可以對應到升序排列。下面我們使用最大堆來討論。
堆的元素處理
根據堆的三個重要的屬性，我們可以得到父結點和子結點的獲取方法，下面用C語言實現：
/
返回父節點和子節點索引/
//返回父結點
int parent(int index)
{
return (index-1)/2;
}
//返回左孩子
int left(int index)
{
return (index<<1)+1;
}
//返回右孩子
int right(int index)
{
return (index+1)<<1;
}</pre>
除了獲取三個屬性之外，我們還應該獲取堆的大小，即元素的個數，下面用C語言實現：
/*
返回堆的大小，指針操作
*/
int heapSize(int *A)
{
int count=0;
while(*(A+count)!='\0') {
count++;
}
return count;
} 堆的性質維護
由于要滿足最大堆的性質，因此當添加一個新元素時，我們需要讓它滿足父結點大于子結點的性質，故堆的性質需要我們去維護，因而，當我們檢查結點i是否滿足要求時，我們應該檢查結點i是否比它的孩子結點都要大，如果比它們大，則可以不用操作；反之，應該將該結點與孩子結點進行交換到新的結點上，進而再次檢查該新結點是否滿足要求，操作方法同上，直到該結點沒有孩子結點為止。
維護堆的性質基本思路如上所述，下面用C語言實現：
/*
維護堆的性質，即把不符合要求的元素重新組織
時間復雜度為logn
*/
void maxHeapify(int *A,int index,int size)
{
int L=left(index);
int R=right(index);
int tmp;
int largestIndex=index;
if(L<size && *(A+index)<*(A+L)) {
largestIndex=L;
}
if(R<size && *(A+largestIndex)<*(A+R)) {
largestIndex=R;
}
if(index!=largestIndex) {
tmp=*(A+index);
*(A+index)=*(A+largestIndex);
*(A+largestIndex)=tmp;
maxHeapify(A,largestIndex);
}
} 如上所示，維護堆的時間復雜度為堆的高度成正比，即logn。類似的，也可以編寫一個minHeapify函數來實現最小堆。
堆的建立
堆的建立即使堆的每個元素都能滿足最大堆的性質的要求，因為葉子結點沒有孩子結點，因而葉子結點無法調用maxHeapify函數，故每個葉子結點都可以看成一個只包含一個元素的堆。
堆的建立可以使用以下一段C語言代碼來實現：
/*
對除沒有子結點的結點進行堆的維護操作，進而
使得一個數組變成一個最大堆
時間復雜度為nlogn
*/
void buildMaxHeap(int *A)
{
int size=heapSize(A);
//找出不是葉子結點的最后一個索引
int need=size/2-1;
int i;
for(i=need;i>=0;i--) {
maxHeapify(A,i,size);
}
} 類似的，可以編寫一個buildMinHeap來建立最小堆。
堆排序算法
通過上面的步驟，我們已經把一個數組建立成為一個最大堆，然而最大堆并不一定是有序堆，因為最大堆只保證了父結點大于子結點，并沒有保證左孩子一定大于右孩子，因此，堆排序就是要使左孩子大于右孩子。但是，我們始終相信，根元素是最大的，因此，我們想先找最大的比較方便，把最大的元素先扔到結尾的葉子結點上，而之前的葉子結點將跑到根結點上并且要滿足堆的性質進行維護即可。
據此，我們可以設計如下算法來實現：
/*
堆排序程序
通過根元素始終是最大的，因此我們倒過來找
從最大的元素依次往最小的元素去排序
*/
void heapSort(int *A)
{
buildMaxHeap(A);
int size=heapSize(A);
int i;
int tmp;
for(i=size-1;i>=0;i--) {
tmp=*A;
*A=*(A+i);
*(A+i)=tmp;
size--;
maxHeapify(A,0,size);
}
} 因此堆排序的時間復雜度為nlogn。
堆排序算法的意義
堆排序是一種優秀的算法，后面我們會看到盡管快速排序的算法性能要優于堆排序，但是堆這一數據結構仍然有重要的實際應用——高校的優先隊列，實際問題例如如何動態保留成績在倒數100名的學生的信息。