void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
//堆向下調(diào)整算法
void AdjustDown(int *a, int n, int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child a[child + 1] && child+1 < n)
            ++child;
        if (a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}

void AdjustUp(int *a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[parent] > a[child])
        {
            swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

int parent = (n-2) / 2;
    //首先對每一個(gè)非葉子節(jié)點(diǎn)進(jìn)行一次向下調(diào)整算法，保證每個(gè)非葉子節(jié)點(diǎn)的
    //孩子都小于它的父節(jié)點(diǎn)，然后可得到最小值，就在堆的頂端的父節(jié)點(diǎn)（也叫做建小堆）
    while (parent >= 0)
    {
        AdjustDown(a, n, parent);
        --parent;
    }

void HeapSort(int *a, int n)
{
    int parent = (n-2) / 2;
    //首先對每一個(gè)非葉子節(jié)點(diǎn)進(jìn)行一次向下調(diào)整算法，保證每個(gè)非葉子節(jié)點(diǎn)的
    //孩子都小于它的父節(jié)點(diǎn)，然后可得到最小值，就在堆的頂端的父節(jié)點(diǎn)（也叫做建小堆）
    while (parent >= 0)
    {
        AdjustDown(a, n, parent);
        --parent;
    }
    int end = n-1;
    while (end>0)
    {
        //將堆頂?shù)臄?shù)與最后的end,以此循環(huán)，進(jìn)行交換就可得到有序序列
        //注意：建小堆，得到降序序列
        swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        --end;
    }
}