原理

将数组构建成大顶堆，然后将根节点与堆底元素交换，最大值排到了末尾，再将剩下的n-1个元素再构成大顶堆，重复操作。

堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

完全二叉树

假设一个二叉树有n层，那么如果第1到n-1层的每个节点都达到最大的个数：2，且第n层的排列是从左往右依次排开的，那么就称其为完全二叉树

分析

最好、最坏，平均都为o(nlogn)

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

代码

void heap_build(int &arr[],int root,int length){
    int lchild = root*2+1;//左子节点索引,从最后一层非叶子节点开始递归的
    if(lchild < length){//保证左子节点不越界
        int flag=lchild;//左右节点中最大值的索引
        int rchild = lchild+1;//右子节点索引
        if(rchild < length){
            if(arr[rchild]>a[flag]) flag=rchild;
        }
        if(a[root]<arr[flag]){
            swap(arr[root],arr[flag]);
            heap_build(arr,flag,length);
        }
    }
}
void head_sort(int &arr[],int len){
    for(int i=(len-1)/2;i>=0;i--) heap_build(arr,i,len);
    for(int j=len-1;j>0;j++){
        swap(arr[0],arr[j]);
        heap_build(arr,0,j)
    }
}