package main

import "fmt"

func main(){

	arr:=[]int{4,8,2,1,6,9,3,5,7,8,1,4}
	dui(arr)
	fmt.Println(arr)
}

func swap(arr []int,a,b int){
	arr[a],arr[b]=arr[b],arr[a]
}

func heapadjust(arr []int,i,m int){

	son:=i*2+1
	for son<m{
		if son+1<m&&arr[son]<arr[son+1]{//首先判断选出左节点大还是右节点大
			son++
		}
		if arr[i]>arr[son]{
			break
		}else{
			swap(arr,i,son)
			i=son
			son=i*2+1
		}
	}
}

func dui(arr []int){
	for i:=len(arr)/2-1;i>=0;i--{	//这里是先变成大顶堆
		heapadjust(arr,i,len(arr))
	}

	for i:=len(arr)-1;i > 0;i--{	//将最大值与最后一个交换，然后对前i-1重新排序
	swap(arr,0,i)
	heapadjust(arr,0,i-1)

	}
}

go实现堆排序