代码：

void HeapSort(int a[], int n){
    int Tmp;
    for (int i = n / 2; i >= 0; i--)
        PercDown(a, i, n);
    /*build a heap; we should know that intinially we put all of the  elements randomly, then
    we begin to percolate down the heap from the last element (n/2) which has the child;
    notice that the elements we should percolate are always all the elements.*/

    /*before the beginning of the formal heapsort, the array has been adjusted to a heap*/

    for (int i = n - 1; i >= 1; i++){
        Tmp = a[i];
        a[i] = a[0];
        a[0] = Tmp;
        /*This step aim at remove the minimum element out of the heap,it‘s important to
        understand the following progress of percolating the heap would not affect this
        element*/
        PercDown(a, 0, i);
        /*We just percolate down the first elements, which would not affect those elements which
        have been sorted*/
    }
}
//下滤算法，从i节点开始调整，n为节点总数，从0开始计算，i节点的子节点为2*i+1,2*i+2
void PercDown(int a[], int i, int n)
{
    int child, temp;

    temp = a[i];/*remember the element which are expected to adjust*/
    child = 2 * i + 1;
    while (child < n){
        if (child + 1 < n && a[child + 1] < a[child])
            child++;
        /*find the smaller child to ensure all two childs are all larger than the parent*/
        if (a[child] >= temp)  break;
        /*if so, the position would be identified.*/
        else{
            a[i] = a[child];//make the smaller child become the parent node
            i = child;//the child position become the new parent position
            child = 2 * i + 1;// the new left child position
        }
    }

    a[i] = temp;
    /*find the appropriate position*/
}

数据结构与算法——堆排序