Golang的Heap使用之谜

hiker_urey · · 3656 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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才是返回队列头元素。

真相只有一个~


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

本文来自:开源中国博客

感谢作者:hiker_urey

查看原文:Golang的Heap使用之谜

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

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