填空题

堆排序

Question

函数heap_sort使用堆排序方法对数组arr进行排序，排序后数据为降序。相关代码如下，请补充缺失部分。

void heap_arrange(int arr[], int cur, int cnt)  //调整为小顶堆

{

    int heaptop_val = arr[cur] //堆顶的值

    while (cur < cnt) {

        int left = 2 * cur + 1

        int right = 2 * cur + 2

        int min = -1

        int min_val = ______ 

        if (left < cnt && arr[left] < min_val) { //检查是否比左节点大

            min = left

            min_val = arr[left]

        }

        if (right < cnt && arr[right] < min_val) {//检查是否比右节点大

            min = right

        }

        if (min == ______) 

            break

        arr[cur] = ______ 

        cur = ______ 

    }

    arr[cur] = ______

}

void heap_sort(int arr[], int cnt)

{

    int i

    for (i = cnt / 2 - 1 i >= 0 --i) {

        heap_arrange(arr, i, cnt)

    }

    for (i = cnt - 1 i > 0 --i) {

        int tmp

        tmp = arr[0]

        arr[0] = arr[i]

        arr[i] = tmp

        heap_arrange(arr, 0, i)

    }

}

输入描述： 第一行为数据个数 第二行为输入数据输入样例： 10 100 32 3 6 24 86 23 90 78 3 输出描述： 排序过程的中间数据，及已经排好序的数据输出样例 origin: 100 32 3 6 24 86 23 90 78 3 make heap: 3 6 3 78 24 86 23 90 100 32 sort i=9 32 6 3 78 24 86 23 90 100 3 3 6 23 78 24 86 32 90 100 3 sort i=8 100 6 23 78 24 86 32 90 3 3 6 24 23 78 100 86 32 90 3 3 sort i=7 90 24 23 78 100 86 32 6 3 3 23 24 32 78 100 86 90 6 3 3 sort i=6 90 24 32 78 100 86 23 6 3 3 24 78 32 90 100 86 23 6 3 3 sort i=5 86 78 32 90 100 24 23 6 3 3 32 78 86 90 100 24 23 6 3 3 sort i=4 100 78 86 90 32 24 23 6 3 3 78 90 86 100 32 24 23 6 3 3 sort i=3 100 90 86 78 32 24 23 6 3 3 86 90 100 78 32 24 23 6 3 3 sort i=2 100 90 86 78 32 24 23 6 3 3 90 100 86 78 32 24 23 6 3 3 sort i=1 100 90 86 78 32 24 23 6 3 3 100 90 86 78 32 24 23 6 3 3 sorted: 100 90 86 78 32 24 23 6 3 3