分享
golang 最小堆排序实现
鼎铭 · · 4107 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
项目中有个模块要大量任务需要控制超时,内部实现了个定时器组件,底层就是基于最小堆算法和时间轮。最小堆算法挺简单的,一个完全二叉树,每个非叶子节点比其两个子节点都小,这就是个最小堆。
该文章后续仍在不断的更新修改中, 请移步到原文地址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。
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信4107 次点击
下一篇:一个可以用手机挖矿的app
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
项目中有个模块要大量任务需要控制超时,内部实现了个定时器组件,底层就是基于最小堆算法和时间轮。最小堆算法挺简单的,一个完全二叉树,每个非叶子节点比其两个子节点都小,这就是个最小堆。
该文章后续仍在不断的更新修改中, 请移步到原文地址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。