大根堆:根大于叶 小根堆:根小于叶
左子叶:
func leftc(n int) int{
return n*2+1
}
右子叶:
func rightc(n int) int{
return n*2+2
}
共三步: 1.假如已经有了二叉树,调整当前根这个分支,采用递归(MaxOrMin值:1大根,2小根)
func adjustHeap(data []int,currentParentIndex int, maxOrMin int){
target:=currentParentIndex
if maxOrMin==1 {
if len(data)>leftc(currentParentIndex) && data[leftc(currentParentIndex)]>data[target]{
target = leftc(currentParentIndex)
}
if len(data)>rightc(currentParentIndex) && data[rightc(currentParentIndex)]>data[target]{
target = rightc(currentParentIndex)
}
}
if maxOrMin==2 {
if len(data)>leftc(currentParentIndex) && data[leftc(currentParentIndex)]<data[target]{
target = leftc(currentParentIndex)
}
if len(data)>rightc(currentParentIndex) && data[rightc(currentParentIndex)]<data[target]{
target = rightc(currentParentIndex)
}
}
if target != currentParentIndex {
data[target],data[currentParentIndex] = data[currentParentIndex],data[target]
adjustHeap(data,target,maxOrMin)
}
}
2.给定一个切片(看成二叉树)来创建大根堆或小根堆,(len-2)/2 是最后一个有子叶的根,从它开始调整。
func createHeap(data []int,maxOrMin int){
for i :=(len(data)-2)/2;i>=0;i--{
adjustHeap(data,i,maxOrMin)
}
}
3.把整个堆的根取出来,之后再创建堆,然后再取,再创建。取出来的就是排序后的值。
func heapSort(data []int, maxOrMin int)[]int{
newData:=make([]int,0)
createHeap(data,maxOrMin)
currentData := data
for len(currentData)>0{
newData = append(newData,currentData[0])
currentData = currentData[1:]
createHeap(currentData,maxOrMin)
}
return newData
}
4.main里面测试一下
func dui(){
data := []int{4,13,14,25,36,265,12,3,4,4,4,16,24,31,41,66,23,64}
k:=10
topK:=make([]int,k)
for i:=0;i<k;i++{
topK[i] = data[i]
}
newData:=heapSort(topK,1)
fmt.Println(newData,topK)
}
topk就是把后面多余的数据一个个跟堆的根去比较,比较成功了,替换根,再重新建堆
取前10名就用小根堆,相当于跟10个里面最弱的比,比得过就进入堆,比不过就滚
取后10名就用大根堆,相当于跟10个弱鸡里面最强的比,比得过就进入堆,比不过就滚
有疑问加站长微信联系(非本文作者)