堆排序

學無涯_思無涯 2013-09-04

展開全文

堆排序與快速排序，歸并排序一樣都是時間復雜度為O(N*logN)的幾種常見排序方法。學習堆排序前，先講解下什么是數(shù)據(jù)結(jié)構(gòu)中的二叉堆。

二叉堆的定義

二叉堆是完全二叉樹或者是近似完全二叉樹。

二叉堆滿足二個特性：

1．父結(jié)點的鍵值總是大于或等于（小于或等于）任何一個子節(jié)點的鍵值。

2．每個結(jié)點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。

當父結(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值時為最大堆。當父結(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值時為最小堆。下圖展示一個最小堆：

由于其它幾種堆（二項式堆，斐波納契堆等）用的較少，一般將二叉堆就簡稱為堆。

堆的存儲

一般都用數(shù)組來表示堆，i結(jié)點的父結(jié)點下標就為(i – 1) / 2。它的左右子結(jié)點下標分別為2 * i + 1和2 * i + 2。如第0個結(jié)點左右子結(jié)點下標分別為1和2。

堆的操作——插入刪除

下面先給出《數(shù)據(jù)結(jié)構(gòu)C++語言描述》中最小堆的建立插入刪除的圖解，再給出本人的實現(xiàn)代碼，最好是先看明白圖后再去看代碼。

堆的插入

每次插入都是將新數(shù)據(jù)放在數(shù)組最后?？梢园l(fā)現(xiàn)從這個新數(shù)據(jù)的父結(jié)點到根結(jié)點必然為一個有序的數(shù)列，現(xiàn)在的任務是將這個新數(shù)據(jù)插入到這個有序數(shù)據(jù)中——這就類似于直接插入排序中將一個數(shù)據(jù)并入到有序區(qū)間中，對照《白話經(jīng)典算法系列之二直接插入排序的三種實現(xiàn)》不難寫出插入一個新數(shù)據(jù)時堆的調(diào)整代碼：

[cpp]view plaincopy
//  新加入i結(jié)點  其父結(jié)點為(i - 1) / 2  
void MinHeapFixup(int a[], int i)  
{  
    int j, temp;  
      
    temp = a[i];  
    j = (i - 1) / 2;      //父結(jié)點  
    while (j >= 0 && i != 0)  
    {  
        if (a[j] <= temp)  
            break;  
          
        a[i] = a[j];     //把較大的子結(jié)點往下移動,替換它的子結(jié)點  
        i = j;  
        j = (i - 1) / 2;  
    }  
    a[i] = temp;  
}  

更簡短的表達為：

[cpp]view plaincopy
void MinHeapFixup(int a[], int i)  
{  
    for (int j = (i - 1) / 2; (j >= 0 && i != 0)&& a[i] > a[j]; i = j, j = (i - 1) / 2)  
        Swap(a[i], a[j]);  
}  

插入時：

[cpp]view plaincopy
//在最小堆中加入新的數(shù)據(jù)nNum  
void MinHeapAddNumber(int a[], int n, int nNum)  
{  
    a[n] = nNum;  
    MinHeapFixup(a, n);  
}  

堆的刪除

按定義，堆中每次都只能刪除第0個數(shù)據(jù)。為了便于重建堆，實際的操作是將最后一個數(shù)據(jù)的值賦給根結(jié)點，然后再從根結(jié)點開始進行一次從上向下的調(diào)整。調(diào)整時先在左右兒子結(jié)點中找最小的，如果父結(jié)點比這個最小的子結(jié)點還小說明不需要調(diào)整了，反之將父結(jié)點和它交換后再考慮后面的結(jié)點。相當于從根結(jié)點將一個數(shù)據(jù)的“下沉”過程。下面給出代碼：

[cpp]view plaincopy
//  從i節(jié)點開始調(diào)整,n為節(jié)點總數(shù) 從0開始計算 i節(jié)點的子節(jié)點為 2*i+1, 2*i+2  
void MinHeapFixdown(int a[], int i, int n)  
{  
    int j, temp;  
  
    temp = a[i];  
    j = 2 * i + 1;  
    while (j < n)  
    {  
        if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的  
            j++;  
  
        if (a[j] >= temp)  
            break;  
  
        a[i] = a[j];     //把較小的子結(jié)點往上移動,替換它的父結(jié)點  
        i = j;  
        j = 2 * i + 1;  
    }  
    a[i] = temp;  
}  
//在最小堆中刪除數(shù)  
void MinHeapDeleteNumber(int a[], int n)  
{  
    Swap(a[0], a[n - 1]);  
    MinHeapFixdown(a, 0, n - 1);  
}  

堆化數(shù)組

有了堆的插入和刪除后，再考慮下如何對一個數(shù)據(jù)進行堆化操作。要一個一個的從數(shù)組中取出數(shù)據(jù)來建立堆吧，不用！先看一個數(shù)組，如下圖：

很明顯，對葉子結(jié)點來說，可以認為它已經(jīng)是一個合法的堆了即20，60， 65， 4， 49都分別是一個合法的堆。只要從A[4]=50開始向下調(diào)整就可以了。然后再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分別作一次向下調(diào)整操作就可以了。下圖展示了這些步驟：

寫出堆化數(shù)組的代碼：

[cpp]view plaincopy
//建立最小堆  
void MakeMinHeap(int a[], int n)  
{  
    for (int i = n / 2 - 1; i >= 0; i--)  
        MinHeapFixdown(a, i, n);  
}  

至此，堆的操作就全部完成了(注1)，再來看下如何用堆這種數(shù)據(jù)結(jié)構(gòu)來進行排序。

堆排序

首先可以看到堆建好之后堆中第0個數(shù)據(jù)是堆中最小的數(shù)據(jù)。取出這個數(shù)據(jù)再執(zhí)行下堆的刪除操作。這樣堆中第0個數(shù)據(jù)又是堆中最小的數(shù)據(jù)，重復上述步驟直至堆中只有一個數(shù)據(jù)時就直接取出這個數(shù)據(jù)。

由于堆也是用數(shù)組模擬的，故堆化數(shù)組后，第一次將A[0]與A[n - 1]交換，再對A[0…n-2]重新恢復堆。第二次將A[0]與A[n – 2]交換，再對A[0…n - 3]重新恢復堆，重復這樣的操作直到A[0]與A[1]交換。由于每次都是將最小的數(shù)據(jù)并入到后面的有序區(qū)間，故操作完成后整個數(shù)組就有序了。有點類似于直接選擇排序。

[cpp]view plaincopy
void MinheapsortTodescendarray(int a[], int n)  
{  
    for (int i = n - 1; i >= 1; i--)  
    {  
        Swap(a[i], a[0]);  
        MinHeapFixdown(a, 0, i);  
    }  
}  

注意使用最小堆排序后是遞減數(shù)組，要得到遞增數(shù)組，可以使用最大堆。

由于每次重新恢復堆的時間復雜度為O(logN)，共N - 1次重新恢復堆操作，再加上前面建立堆時N / 2次向下調(diào)整，每次調(diào)整時間復雜度也為O(logN)。二次操作時間相加還是O(N * logN)。故堆排序的時間復雜度為O(N * logN)。STL也實現(xiàn)了堆的相關函數(shù)，可以參閱《STL系列之四 heap 堆》。

注1 作為一個數(shù)據(jù)結(jié)構(gòu)，最好用類將其數(shù)據(jù)和方法封裝起來，這樣即便于操作，也便于理解。此外，除了堆排序要使用堆，另外還有很多場合可以使用堆來方便和高效的處理數(shù)據(jù)，以后會一一介紹。

轉(zhuǎn)載請標明出處，原文地址：http://blog.csdn.net/morewindows/article/details/6709644