golang 堆排序

堆排序可以很好解决TopK问题

时间复杂度 N(logN)，不稳定排序，相同大小数据仍可能交换位置

寻找海量数据中最大的100个数据，可以建立容量100的小顶堆，然后将后面的数据与堆顶最小值比较，

如果比它大，进行交换重新将堆进行调整，后面数据以此类推，可以得到top 100的数据

package main

import "fmt"

//想得到从小到大的排序结果，需要构建大顶堆，然后将堆顶最大值与最后的数据交换，
//依次进行，可以得到顺序的结果
func HeapSort(nums []int)  {
	
	N:=len(nums)-1
	//从底部到顶部构建大顶堆，最后一个非叶子节点开始
	for i:=N/2;i>=0;i--{
		sink(nums,i,N)
	}
	
	//将堆顶值和末尾交换，重新调整堆
	for i:=N;i>=0;i--{
		wap(nums,0,i)
		sink(nums,0,i-1)//交换之后，数组最后一位不算在堆内，需要减1操作
	}
	
	//不同写法，结果一样
	/*for N>=0{
		wap(nums,0,N)
		N--
		sink(nums,0,N)
	}*/
}

func sink(nums []int,k,N int)  {
	for{
		i:=2*k+1
		if i>N{
			break
		}
		//找左右子节点最大值
		if i+1<=N&&nums[i+1]>nums[i]{
			i++
		}
		//已经大于最大值，不需要再交换
		if nums[k]>=nums[i]{
			break
		}
		wap(nums,k,i)
		k = i //继续向上调整
	}
}

func wap(nums []int,x,y int){
	nums[x],nums[y] = nums[y],nums[x]
}

func main()  {
	s := []int{-1,9, 0, 6, 5, 8, 2, 1, 7, 4, 3}
	fmt.Println(s)
	HeapSort(s)
	fmt.Println(s)
}