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