文档章节

Golang的Heap使用之谜

h
 hiker_urey
发布于 2017/11/14 22:57
字数 952
阅读 211
收藏 8
点赞 0
评论 0

Go语言的官方package里面提供了"container/heap",在该package里面定义了Heap(堆)这一数据结构的使用接口。只要自定义的数据类型实现了标准接口,可以很方便的对自定义的数据类型在堆中进行排序了。

堆结构的接口为:

type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

同时sort.Interface接口为:

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

因此为了使用自定义的堆结构,需要定义5个接口函数。

在实践中期望构造一个使用堆排序的定时器队列,能够按照堆顶的元素快速获得最近的任务触发时间:

type element struct {
	TaskId    string
	Expire    time.Time
	...
}

type eleHeap []*element

构造自定义的堆结构接口:

func (h eleHeap) Len() int           { return len(h) }
func (h eleHeap) Less(i, j int) bool { return h[i].Expire.Before(h[j].Expire) }
func (h eleHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *eleHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(*element))
}

func (h *eleHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]		// 为什么Pop是取slice最末元素?
	*h = old[0 : n-1]   // 难道Golang的堆不是最小堆吗?
	return x
}

在此之后就可以使用Heap的公共函数来对自定义的堆结构进行Pop和Push操作了。

to := time.NewTimer(WaitInterval)
hp := &eleHeap{} // 定义变量
heap.Init(hp)	 // 堆结构初始化
for {
	select {
		case ele := <-TaskChan:
			heap.Push(hp, ele) // 入堆
			to.Reset(0)
		case <-to.C:
			for hp.Len() != 0 {
				ele, ok := heap.Pop(hp).(*element) // 出堆
				if ok {
					if time.Now().Before(ele.Expire) {
						heap.Push(hp, ele) // 时辰未到,再次入堆
						to.Reset(ele.Expire.Sub(now))
						break
					}
					// time expired, do task
					...
				}
			}
		}
	}
}

在使用堆的过程中,对于为何在自定义的Pop过程中,取出的是队列中最末元素有些不解。自定义的Push过程也是将元素放在最末,那么Pop过程理所应当从队列头部取出经过上浮、下沉操作后堆中最小(大)的元素。经过查看"container/heap"的源码,终于揭开了这一谜题。

首先看一下堆的上浮、下沉操作:

func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {
			break
		}
		// 在上浮过程中,从较大的节点j开始,与其父节点进行比较
		// 若不小于其父节点,则与其父节点进行交换
		h.Swap(i, j)
		j = i
	}
}

func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
			j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
		// 在下沉过程中,从较小的i0节点开始,与其两个子节点进行比较
		// 若小于其中一个子节点,则与较小的子节点进行交换
		h.Swap(i, j)
		i = j
	}
	return i > i0
}

上浮和下沉过程还是十分标准的,再看一下Push和Pop过程:

func Push(h Interface, x interface{}) {
	h.Push(x)        // 使用自定义的Push接口,将元素放入队列尾部
	up(h, h.Len()-1) // 将新放入的元素进行上浮操作
}

func Pop(h Interface) interface{} {
	n := h.Len() - 1
	h.Swap(0, n)     // 交换队列中头和尾元素
	down(h, 0, n)    // 将原队列的尾元素在h.Len() - 1的新队列中进行下沉
	return h.Pop()   // 弹出交换后的尾元素
}

由此可见,对于自定义Pop函数理解的错误还是因为自身对于堆结构的思维定势导致的。 如果Heap.Pop过程中,先获得头元素的值,再将尾元素放入队列头进行下沉,则自定义的Pop才是返回队列头元素。

真相只有一个~

© 著作权归作者所有

共有 人打赏支持
h
粉丝 1
博文 15
码字总数 12905
作品 0
广州
程序员
golang 标准库 container/ring 及 container/heap

由于目前golang 没有提供泛型机制,所以通用容器实现基本和 c 类似,golang 用 interface{} 做转接, c 用 void * 转接。 ring 包实现循环双向链表: type Ring struct { next, prev *Ring ...

yujian0231 ⋅ 2015/03/18 ⋅ 0

golang内存分配

golang内存分配 new一个对象的时候,入口函数是malloc.go中的newobject函数 这个函数先计算出传入参数的大小,然后调用mallocgc函数,这个函数三个参数,第一个参数是对象类型大小,第二个参...

王二狗子11 ⋅ 01/07 ⋅ 0

5个GoLang 应用优化措施

这是Go 的开发者之一 Dave Cheney 介绍的5个GoLang 优化措施: 清晰赋值类型 比如确认一个数不会超过 uint32 就不要使用int,下表是数值的范围 赋值: 数值能用小的用小的,尽量让数值留在C...

wangdy ⋅ 2016/07/12 ⋅ 0

cgo 调用练习, 简单愚蠢命令行词典

在go 的程序中调用 c 代码, golang 提供了两种方法: cgo, swing 。gstreamer 是开源跨平台的多媒体框架库,主要是在gnome 基础核心库 glib 之上构建。下面有一个简单的使用cgo 包装 gstrea...

yujian0231 ⋅ 2015/02/02 ⋅ 0

我的一次失败的创业 3

[我的一次失败的创业 1][1] [我的一次失败的创业 2][2] 在图谜的开发过程中,我们一共发布了5个版本。我们发版的速度可以说是越来越快。最初是两个月才发一个版本,后来几乎几天就可以完成一...

costaxu ⋅ 2012/12/01 ⋅ 15

Golang profiling and optimizing

本文总结自Profiling and Optimizing Go,对应的PPT,有梯子的可以直接看视频,没梯子的也可以看下这篇文章:) 。 Golang的runtime内建了强大的分析工具pprof,能帮助我们对程序运行时的CPU、...

Rokety Yang ⋅ 01/27 ⋅ 0

golang 实现斐波那契堆

二叉堆提供了o(lgn) 时间的插入, 删除最小,降级等操作,o(n) 时间的合并操作; 斐波那契堆提供了更优操作时间界限:o(1) 插入, o(lgn) 删除最小, o(lgn) 删除, o(1)合并。 根据算法导论上...

yujian0231 ⋅ 2015/03/18 ⋅ 0

[转]编写高性能的Go代码的最佳实践

[转]编写高性能的Go代码的最佳实践 鸟窝2017-12-291 阅读 Go 原文: go-perfbook/performance This document outlines best practices for writing high-performance Go code. At the moment......

鸟窝 ⋅ 2017/12/29 ⋅ 0

读书笔记图灵传,算法

三种算法 桶排序O(N+M) 冒泡排序O(N2) 快速排序O(NlogN) 桶排序的速度最快 队列 栈 回文 深度优先搜索算法 斯坦福大学研究图的连通性 广度优先搜索 1959年 图的深度和广度优先搜索 图的深度优...

writeademo ⋅ 2016/08/28 ⋅ 0

Golang之interface

一、什么是interface 简单地说,interface是一组method的组合,可以通过interface来定义对象的一组行为。 二、interface类型 interface类型定义了一组方法,如果某个对象实现了某个接口的所有...

xumaojun ⋅ 01/30 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

PHP语言系统ZBLOG或许无法重现月光博客的闪耀历史[图]

最近在写博客,希望通过自己努力打造一个优秀的教育类主题博客,名动江湖,但是问题来了,现在写博客还有前途吗?面对强大的自媒体站点围剿,还有信心和可能型吗? 至于程序部分,我选择了P...

原创小博客 ⋅ 14分钟前 ⋅ 0

IntelliJ IDEA 2018.1新特性

工欲善其事必先利其器,如果有一款IDE可以让你更高效地专注于开发以及源码阅读,为什么不试一试? 本文转载自:netty技术内幕 3月27日,jetbrains正式发布期待已久的IntelliJ IDEA 2018.1,再...

Romane ⋅ 40分钟前 ⋅ 0

浅谈设计模式之工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端暴露创建逻...

佛系程序猿灬 ⋅ 今天 ⋅ 0

Dockerfile基础命令总结

FROM 指定使用的基础base image FROM scratch # 制作base image ,不使用任何基础imageFROM centos # 使用base imageFROM ubuntu:14.04 尽量使用官方的base image,为了安全 LABEL 描述作...

ExtreU ⋅ 昨天 ⋅ 0

存储,对比私有云和公有云的不同

导读 说起公共存储,很难不与后网络公司时代的选择性外包联系起来,但尽管如此,它还是具备着简单和固有的可用性。公共存储的名字听起来也缺乏专有性,很像是把东西直接堆放在那里而不会得到...

问题终结者 ⋅ 昨天 ⋅ 0

C++难点解析之const修饰符

C++难点解析之const修饰符 c++ 相比于其他编程语言,可能是最为难掌握,概念最为复杂的。结合自己平时的C++使用经验,这里将会列举出一些常见的难点并给出相应的解释。 const修饰符 const在c...

jackie8tao ⋅ 昨天 ⋅ 0

聊聊spring cloud netflix的HystrixCommands

序 本文主要研究一下spring cloud netflix的HystrixCommands。 maven <dependency> <groupId>org.springframework.cloud</groupId> <artifactId>spring-clo......

go4it ⋅ 昨天 ⋅ 0

Confluence 6 从其他备份中恢复数据

一般来说,Confluence 数据库可以从 Administration Console 或者 Confluence Setup Wizard 中进行恢复。 如果你在恢复压缩的 XML 备份的时候遇到了问题,你还是可以对整个站点进行恢复的,如...

honeymose ⋅ 昨天 ⋅ 0

myeclipse10 快速搭建spring boot开发环境(入门)

1.创建一个maven的web项目 注意上面标红的部分记得选上 2.创建的maven目录结构,有缺失的目录可以自己建立目录补充 补充后 这时候一个maven的web项目创建完成 3.配置pom.xml配置文件 <proje...

小海bug ⋅ 昨天 ⋅ 0

nginx.conf

=========================================================================== nginx.conf =========================================================================== user nobody; #......

A__17 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部