（1）堆的概念

所謂堆，它是一個數(shù)組，也能夠被看成一個近似的全然二叉樹。樹上每一個結(jié)點相應(yīng)數(shù)組的一個元素。二叉堆分為二種：最大堆和最小堆。本文主要介紹最大堆，最小堆類似。最大堆的特點：對于隨意某個結(jié)點，該結(jié)點的值大于左孩子、右孩子的值，可是左右孩子的值沒有要求。

（2）堆排序算法

堆排序算法調(diào)用函數(shù)Build_max_heap將輸入數(shù)組array[1..n]建立成堆。當中n表示數(shù)組長度。由于建立堆后，數(shù)組的最大元素被存放在根節(jié)點A[1]，通過將A[1]與數(shù)組最后一個元素進行交換。將最大元素后移，實現(xiàn)排序。

可是，交換后新的根節(jié)點可能不滿足堆的特點，所以須要調(diào)用子函數(shù)Max_heapify對剩余的數(shù)組元素進行最大堆性質(zhì)的維護。堆排序算法。通過不斷反復(fù)這個過程(n-1)次，實現(xiàn)數(shù)組的從小到大排序(由于採用最大堆)。

對于上面提及的兩個子函數(shù)進行簡要介紹。

函數(shù)Build_max_heap的作用：建堆。

由于子數(shù)組A(n/2+1..n)是樹的葉子節(jié)點，不須要進行堆的維護。

所以。僅僅須要對A[1..n/2]數(shù)組元素進行維護。就可構(gòu)建堆。

函數(shù)Max_heapify的作用：維護堆。過程：如果A[i]表示樹的某個結(jié)點，則A[2*i]是其左孩子，A[2*i+1]是其右孩子。接下來，比較三者大小挑選出最大元素的下標，存放于largest。然后。推斷(largest==i)嗎。若不滿足則進行元素交換。將大的元素上移。

此時，以A[largest]為根節(jié)點的子樹可能不滿足堆的性質(zhì)，所以須要遞歸調(diào)用自身。

（3）動圖演示：

（4）C語言代碼實現(xiàn)如下：

#include <stdio.h>#include <stdlib.h>void swap(int *arr,int i, int k) {
    int temp = arr[i];
    arr[i] = arr[k];
    arr[k] = temp;}void max_heapify(int *arr, int start, int end) {
    //建立父節(jié)點下標和子節(jié)點下標
    int dad = start;

    int son = dad * 2 + 1;

    while (son <= end) 
    {   //若子節(jié)點下標在范圍內(nèi)才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節(jié)點大小，選擇最大的
        {
            son++;
        
        }

        if (arr[dad] > arr[son]) //如果父節(jié)點大于子節(jié)點代表調(diào)整完畢,直接跳出
        {
            return;
        }   
        else 
        {   //否則交換父子節(jié)點的值再繼續(xù)左右子節(jié)點值得比較
            swap(arr,dad, son);
            printf("dad=%d--son=%d\n",dad,son);
            dad = son;
            son = dad * 2 + 1;
        }
            
    }}void heap_sort(int *arr, int len) {
    int i;
    //初始化，i從最后一個父節(jié)點開始調(diào)整
    for (i = len / 2 - 1; i >= 0; i--)
    {
        max_heapify(arr, i, len - 1);
        
    }


    for (i = len - 1; i > 0; i--) 
    {
        swap(arr,0, i);

        max_heapify(arr, 0, i - 1);
    }}int main(int argc, char const *argv[]){
    int arr[] = {5,3,8,1,6};

    int len = sizeof(arr) / sizeof(int);

    heap_sort(arr, len);

    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }
        
    printf("\n");
    
    return 0;}

如果我們編譯并運行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

dad=1--son=4
dad=0--son=2
dad=0--son=1
dad=0--son=2
dad=0--son=1
1 3 5 6 8