堆排序的分析及實現

（二叉）堆是一個數組，它可以被看成一個近似的完全二叉樹。二叉堆可以分為兩種形式：最大堆和最小堆。若將記錄按從大到小排列，建“小”頂堆。若將記錄按從小到大排，建“大”頂堆。

說明：在堆排序算法中，我們使用的是最大堆，最小堆通常用於構造優先隊列。

算法分析：時間復雜度是O(nlogn)。堆排序屬於原址排序：任何時候都只需要常數個額外的元素空間存儲臨時數據。堆排序是不穩定的排序算法。

#include <stdio.h>
#define LEFT(i)        2 * i
#define RIGHT(i)    2 * i + 1

void MaxHeapAjust(int A[], int i, int len)            //調整節點i滿足最大堆性質
{
    int l = LEFT(i);
    int r = RIGHT(i);
    int largest, tmp;

    if (l <= len && A[l - 1] > A[i - 1])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if (r <= len && A[r - 1] > A[largest - 1])
    {
        largest = r;
    }

    if (i != largest)
    {
        tmp = A[i - 1];                       
        A[i - 1] = A[largest - 1];
        A[largest - 1] = tmp;

        MaxHeapAjust(A, largest, len);
    }
}

void BuildMaxHeap(int A[], int len)                    //構造最大堆
{
    for (int i = len / 2; i > 0; i--)
    {
        MaxHeapAjust(A, i, len);
    }
}

void HeapSort(int A[], int len)                        //堆排序
{
    int tmp;
    BuildMaxHeap(A, len);
    for (int i = len; i > 1; i--)
    {
        tmp = A[i - 1];
        A[i - 1] = A[0];
        A[0] = tmp;

        MaxHeapAjust(A, 1, i - 1);
    }
}

int main(void)
{
    int A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    HeapSort(A, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");

    return 0;
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm