【数据结构与算法】堆排序算法实现

一、堆排序思想

假定我们要排序的内容存放在数组中，希望按照从小到大的顺序排列。此时需要一个（max）heap协助。

首先，把数组中的内容构建成堆。那么，堆顶的数即为数组的最大值。

其次，删除堆顶，并且对堆重新排序，直至堆中的数都被删除。依次删除的值即为从大到小排序。

具体的算法思想参见《数据结构与算法》一书，7.5节内容。

二、c代码实现

#include <stdio.h>
#include <stdlib.h>

#define LeftChild(i) (2 * ( i ) + 1)

typedef int ElementType;

void Swap(ElementType *x, ElementType *y)
{
    ElementType t;
    t = *x;
    *x = *y;
    *y = t;
}

void PrintHeap(ElementType A[], int N)
{
    int i;
    for(i = 0; i < N; i++)
    {
        printf("%d\t", A[i]);
    }
    printf("\n");
}

void PercolateDown(ElementType A[], int i, int N)
{
    ElementType Tmp;
    int Child;
    
    for(Tmp = A[i]; LeftChild(i) < N; i = Child)
    {
        Child = LeftChild(i);
        //Find the larger child
        if(Child != N-1 && A[LeftChild(i)] < A[LeftChild(i) + 1])
          Child++;
        //if the child is larger than Tmp,
        //child move to the upper level
        if(A[Child] > Tmp)
          A[i] = A[Child];
        else
          break;
    }
    A[i] = Tmp;
}

void HeapSort(ElementType A[], int N)
{
    int i;
    //Build Heap
    for(i = N / 2; i >= 0; i--)
      PercolateDown(A, i, N);
    
    //Swap the root of the heap element with last element
    //percolate down the new root of the heap
    //rebuild the heap in order
    for(i = N - 1; i > 0; i--)
    {
        //Delete Max
        Swap( &A[0], &A[i] );
        PercolateDown(A, 0, i);
    }
}

int main()
{
    int array[] = {31, 41, 59, 26, 53, 58, 97};
    PrintHeap(array, sizeof(array)/sizeof(int));
    
    HeapSort(array, sizeof(array)/sizeof(int));
    printf("After heap sort:\n");
    PrintHeap(array, sizeof(array)/sizeof(int));
    return 0;

}