Go教程

go container/heap包浅析

本文主要是介绍go container/heap包浅析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

go container/heap包提供了堆的实现。

更详细的定义见下面的链接

Go语言标准库文档中文版 | Go语言中文网 | Golang中文社区 | Golang中国 (studygolang.com)

这里主要讲下怎么使用这个包来实现最小堆和最大堆

首先要定义一个满足下面这个接口的类型

type Interface interface {
    sort.Interface
    Push(x interface{}) // 向末尾添加元素
    Pop() interface{}   // 从末尾删除元素
}

这意味着,有两种定义数据类型的方式,即是否复用sort包里的数据类型。

1.复用的情况,定义如下

type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }

  

2.不复用的情况

 

type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

  

唯一需要注意的是Pop的实现,它是要删除数组末尾的元素,而非开头的元素。因为这个Pop是让heap包的Pop去调用的。heap包里Pop实际的逻辑是,先把堆的根节点值和数组末尾节点的值进行交换,然后再删除末尾的节点(调用我们实现的Pop),调整根节点。

 

另外,这个是最小堆的实现,如果想实现最大堆,有几种办法。

  1. 把Less的实现修改下,即返回结果取反。那么实际实现的就是最大堆了
  2. 把存入堆的值取负,那么这时候,最小堆其实就是绝对值的最大堆,取数据的时候再取负就行了。
  3. 最正规的办法,似乎是使用sort.Reverse

 

这篇关于go container/heap包浅析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!