新手golang实现堆排序及topK问题

lwcbest · 2020-02-06 18:07:11 · 928 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2020-02-06 18:07:11 的主题,其中的信息可能已经有所发展或是发生改变。

大根堆:根大于叶 小根堆:根小于叶

左子叶:

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个弱鸡里面最强的比,比得过就进入堆,比不过就滚


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

928 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传