Heap Sort

Reference

1. 堆排序
2. Sorting algorithms/Heapsort
3. 演算法: 堆積排序法(Heap Sort)

void swap(int* a, int* b) {
    int t= *b;
    *b = *a;
    *a = t;
}

//最大堆積化(Max Heapify)
//Have parent node bigger than son node
void MaxHeapify(int *a, int start, int n)
{
    int dad = start;
    int son = dad * 2 + 1;

    while(son < n) {
        if(son+1 < n && a[son]<a[son+1])
            son++;
        if(a[dad] > a[son])
            return;
        else {
            swap(&a[dad], &a[son]);
            dad = son;
            son = dad * 2 + 1;
        }

    }
}

//int *a        Array[]
//int n         size of Array

void HeapSort(int *a, int n)
{
    int i;
    for(i = n/2-1; i >= 0; i--) {       //對有子節點的節點做最大堆積化(Max Heapify)
        MaxHeapify(a, i, n);
    }
    for(i = n-1; i>0; i--){             //排序,第一個(最大值)跟最後一個交換,接著做Max Heapify
        swap(&a[0], &a[i]);
        MaxHeapify(a, 0, i);
    }
}