/*
7.堆排序
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)
*/

/*  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2 n是数组的大小*/
void MinHeapFixdown(int a[], int i, int n) {
    for(int j = 2 * i + 1; j < n; i = j, j = 2 * i + 1) {
        if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的
            j++;
        if (a[j] >= a[i])
            break;
        swap(a[i], a[j]);
    }
}


void MinheapsortTodescendarray(int a[], int n) {
    //建立最小堆
    for (int i = n / 2 - 1; i >= 0; i--)
        MinHeapFixdown(a, i, n);

    //对最小堆进行删除操作，即排序
    for (int i = n - 1; i >= 1; i--) {
        swap(a[i], a[0]);
        MinHeapFixdown(a, 0, i);
    }
}