堆排序的思想借助了二叉排序树时间复杂度：O(NlgN)，空间复杂度O(N)

堆本质上是一个完全二叉树，所以构建堆的时候可以借助二叉树递归构建办法，构建堆的代码有：

 
 // 这里假设index就是最小的元素值然后和孩子比较
 // 左孩子小，需要调整和左孩子的关系
 // 右孩子小调整右孩子
 // 表示有调整，需要交换孩子与父节点嘚位置
 
 // 这个时候调整arr[min]后，很有可能堆不满足小顶堆所以递归判断
 

 构建大顶堆，则在比较的时候相反就行
 
 

 

 
 

 构建完堆以后 开始做排序。洇为堆顶元素具有特殊性（最大或者最小）所以第一次比较用数组最后一位，与堆顶元素比较可以确定最后一位是有序的；然后调整堆，用倒数第二位与堆顶元素比较得到倒数第二位和最后一位构成一个有序的数组；依次循环，直到数组元素第一个比较完成
 
 

 在构建堆的时候，因为左右孩子是2倍关系所以调整堆只需要数组长度的一半遍历就行。
 
 

 //调整后再进行小顶堆调整