大顶堆：根节点不小于左右子节点
小顶堆：根节点不大于左右子节点
排序过程：
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;
}
