golang 最小堆排序实现

鼎铭 · · 3549 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

项目中有个模块要大量任务需要控制超时，内部实现了个定时器组件，底层就是基于最小堆算法和时间轮。最小堆算法挺简单的，一个完全二叉树，每个非叶子节点比其两个子节点都小，这就是个最小堆。

该文章后续仍在不断的更新修改中，请移步到原文地址http://dmwan.cc

实现代码如下:

package main

import (
    "fmt"
)

func heapSort(input []int){
    inputLen := len(input)
    if inputLen == 0 {
        return
    }
    for i:=0; i<inputLen; i++{
        minAjust(input[i:])
    }
}

func minAjust(input []int){
    inputLen := len(input)
    if inputLen <= 1{
        return
    }
    for i:= inputLen/2 -1; i>=0; i--{
        if (2*i+1 <= inputLen-1) && (input[i] >= input[2*i+1]){
           input[i], input[2*i+1] = input[2*i+1], input[i]
        }
        if (2*i+2<= inputLen-1) && (input[i] >= input[2*i+2]){
            input[i], input[2*i+2] = input[2*i+2], input[i]
        }
    }
}

func main (){
    testSlice := []int {2,3,1,4,5,6,2,1,23,43,1,32,3,5,2,1,8,54,4,0}
    fmt.Println(testSlice)
    heapSort(testSlice)
    fmt.Println(testSlice)
}

满足公式 A[i]<A[2*i+1] &&A[i]<A[2*i+2] 即可，这个如果想不起来，画画图就ok。

有疑问加站长微信联系（非本文作者）