#include <stdio.h>

/*遍历*/

void tranvase(int * arr, int len){

    int i;

    for(i=1; i<=len; i++){

        printf("%d、", arr[i]);

    }

    printf("\n");

}

/*调整堆*/

void tiaozhengdui(int * arr, int root, int end){ //root 为根坐标 end为最后元素坐标

    int j;

    j = 2*root; //root的左子树

    int temp = arr[root]; //临时保存根节点值

    /*比较左子树值和右子树值*/

    if((j+1)<=end && arr[j]<arr[j+1]){

        j=j+1;

    }

    //j 指向子树最大值的位置

    // 继续比较 该最大值 和 它的 子树值进行比较

    while(j<=end){

        if(temp<arr[j]){ //根节点值<子树最大值  互换值

                arr[root] = arr[j];

                root = j;

                j = 2*j;

                 /*比较左子树值和右子树值*/

                if((j+1)<=end && arr[j]<arr[j+1]){

                    j=j+1;

                }

        }else{

            j = end+1; //退出

        }

    }

    arr[root] = temp;

}

/*堆排序*/

void stackSort(int * arr, int len){

        int i,j,temp;

        //初始化堆

        for(i=len/2; i>=1; i--){

            tiaozhengdui(arr, i, len);

        }

        /*换根和最后元素的值*/

        for(j=len; j>=2; j--){

             temp = arr[1]; //临时存储根节点最大值

             arr[1] = arr[len]; //根节点保存最后一个结点的值

             arr[len]=temp; //最后一个结点保存最大值

             len = len-1;

             tiaozhengdui(arr, 1, len); //继续调整堆

    }

}

int main(){

    int arr[10] = { 0, 12, 1, 33, 23, 23, 4, 2, 445, 2};

    tranvase(arr, 9);

    stackSort(arr, 9);

    tranvase(arr, 9);

    return 0;

}