白話經典算法系列之七 堆與堆排序

 堆排序與​​高速排序​​，​​歸并排序​​一樣都是時間複雜度為O(N*logN)的幾種常見排序方法。學習堆排序前，先解說下什麼是資料結構中的二叉堆。

二叉堆的定義

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

二叉堆滿足二個特性：

1．父結點的鍵值總是大于或等于（小于或等于）不論什麼一個子節點的鍵值。

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

當父結點的鍵值總是大于或等于不論什麼一個子節點的鍵值時為最大堆。當父結點的鍵值總是小于或等于不論什麼一個子節點的鍵值時為最小堆。下圖展示一個最小堆：

因為其他幾種堆（二項式堆，斐波納契堆等）用的較少，一般将二叉堆就簡稱為堆。

堆的存儲

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

堆的操作——插入删除

以下先給出《資料結構C++語言描寫叙述》中最小堆的建立插入删除的圖解，再給出本人的實作代碼，最好是先看明确圖後再去看代碼。

堆的插入

每次插入都是将新資料放在數組最後。能夠發現從這個新資料的父結點到根結點必定為一個有序的數列，如今的任務是将這個新資料插入到這個有序資料中——這就相似于直接插入排序中将一個資料并入到有序區間中，對比​​《白話經典算法系列之二 直接插入排序的三種實作》​​不難寫出插入一個新資料時堆的調整代碼：

//  新增加i結點  其父結點為(i - 1) / 2
void MinHeapFixup(int a[], int i)
{
    int j, temp;

    temp = a[i];
    j = (i - 1) / 2;      //父結點
    while (j >= 0 && i != 0)
    {
        if (a[j] <= temp)
            break;

        a[i] = a[j];     //把較大的子結點往下移動,替換它的子結點
        i = j;
        j = (i - 1) / 2;
    }
    a[i] = temp;
}      

更簡短的表達為：

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]);
}      

插入時：

//在最小堆中增加新的資料nNum
void MinHeapAddNumber(int a[], int n, int nNum)
{
  a[n] = nNum;
  MinHeapFixup(a, n);
}      

堆的删除

按定義，堆中每次都僅僅能删除第0個資料。為了便于重建堆，實際的操作是将最後一個資料的值賦給根結點，然後再從根結點開始進行一次從上向下的調整。調整時先在左右兒子結點中找最小的，假設父結點比這個最小的子結點還小說明不須要調整了，反之将父結點和它交換後再考慮後面的結點。相當于從根結點将一個資料的“下沉”過程。以下給出代碼：

//  從i節點開始調整,n為節點總數 從0開始計算 i節點的子節點為 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];     //把較小的子結點往上移動,替換它的父結點
        i = j;
        j = 2 * i + 1;
    }
    a[i] = temp;
}
//在最小堆中删除數
void MinHeapDeleteNumber(int a[], int n)
{
    Swap(a[0], a[n - 1]);
    MinHeapFixdown(a, 0, n - 1);
}      

堆化數組

有了堆的插入和删除後，再考慮下怎樣對一個資料進行堆化操作。要一個一個的從數組中取出資料來建立堆吧，不用！先看一個數組，例如以下圖：

非常明顯，對葉子結點來說，能夠覺得它已經是一個合法的堆了即20，60， 65， 4， 49都各自是一個合法的堆。僅僅要從A[4]=50開始向下調整就能夠了。然後再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分别作一次向下調整操作就能夠了。下圖展示了這些步驟：

寫出堆化數組的代碼：

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

至此，堆的操作就所有完畢了(注1)，再來看下怎樣用堆這種資料結構來進行排序。

堆排序

首先能夠看到堆建好之後堆中第0個資料是堆中最小的資料。取出這個資料再運作下堆的删除操作。這樣堆中第0個資料又是堆中最小的資料，反複上述步驟直至堆中僅僅有一個資料時就直接取出這個資料。

因為堆也是用數組模拟的，故堆化數組後，第一次将A[0]與A[n - 1]交換，再對A[0…n-2]又一次恢複堆。第二次将A[0]與A[n – 2]交換，再對A[0…n - 3]又一次恢複堆，反複這種操作直到A[0]與A[1]交換。因為每次都是将最小的資料并入到後面的有序區間，故操作完畢後整個數組就有序了。有點相似于​​直接選擇排序​​。

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

注意使用最小堆排序後是遞減數組，要得到遞增數組，能夠使用最大堆。

因為每次又一次恢複堆的時間複雜度為O(logN)，共N - 1次又一次恢複堆操作，再加上前面建立堆時N / 2次向下調整，每次調整時間複雜度也為O(logN)。二次操作時間相加還是O(N * logN)。故堆排序的時間複雜度為O(N * logN)。STL也實作了堆的相關函數，能夠參閱《​​STL系列之四 heap 堆​​》。

注1 作為一個資料結構，最好用類将其資料和方法封裝起來，這樣即便于操作，也便于了解。此外，除了堆排序要使用堆，另外還有非常多場合能夠使用堆來友善和高效的處理資料，以後會一一介紹。