基本原理

1.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆。

2.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端。

3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序 。

代码实现

 package sort

//Heap 堆排序
func Heap(nums []int) {
lenght := len(nums)
for i := 0; i < lenght; i++ {
lastlen := lenght - i
sortMax(nums, lastlen)
if i < lenght {
nums[0], nums[lastlen-1] = nums[lastlen-1], nums[0] // 首尾交换
}
}
}

func sortMax(arr []int, length int) []int {
if length <= 1 {
return arr
}

depth := length/2 - 1 // 二叉树深度
for i := depth; i >= 0; i-- {
topmax := i // 假定最大位置就在i
leftchild := 2*i + 1
rightchild := 2*i + 2

if leftchild <= length-1 && arr[leftchild] > arr[topmax] { // 防止越过界限
topmax = leftchild
}

if rightchild <= length-1 && arr[rightchild] > arr[topmax] { // 防止越过界限
topmax = rightchild
}

if topmax != i {
arr[i], arr[topmax] = arr[topmax], arr[i]
}
}

return arr
}