堆排序

大顶堆：根节点不小于左右子节点
小顶堆：根节点不大于左右子节点
排序过程：
1.初始建堆
将待排序的n个关键字放到一颗完全二叉树中，从树的最后一个非叶子节点开始调整堆，直到树的根节点排成堆为止。
2.调整成新堆
（1）交换堆顶元素a[0]和a[n-1]，得到无序区（a[0],a[1]...a[n-2]）和有序区（a[n-1]）
（2）交换之后可能会破坏堆，需要对无序区调整成新堆。
（3）重复交换堆顶元素和无序区最后一个元素，再调整新堆，直到节点全部有序。

完全二叉树的性质：
当前节点为i时，左孩子节点：2i+1，右孩子节点：2i+2
最后一个非叶子节点 length/2-1

void HeapAdjust(int a[], int parent, int length){
    int temp = a[parent];
    int child = parent * 2 + 1;
    while(child<length){
        if(child+1<length&&a[child+1]>a[child])
        {
            child +=1;
        }
        if(temp>a[child])
            break;
        else{
            a[parent]=a[child];
            parent = child;
            child = 2 * parent + 1;
        }
        
    }
    a[parent] = temp;
    
} 
void HeapSort(int a[],int length){
    //初始化堆
    int i;
    for(i = length/2-1;i>=0;i--){
        HeapAdjust(a,i,length);
    }

    //排序 
    for(i=length-1;i>0;i--){

        int temp = a[i];  //交换a[i]和a[0]元素，再从上向下调整堆 
        a[i] = a[0];
        a[0] = temp;
        HeapAdjust(a,0,i);
        for(int i=0;i<10;i++){
            cout<<a[i];
        }
        cout<<endl;
    } 
}
int main(){
    int a[10]={2,1,2,4,5,1,2,7,5,9};
    HeapSort(a,10);
    for(int i=0;i<10;i++){
        cout<<a[i];
    }
    return 0;
}