Golang container.heap 包详解

container/heap 包提供了一个堆的实现，堆可以被当作最小堆或者最大堆使用，最小堆可以用来实现优先队列，最大堆可以用来实现堆排序。

以下是使用 container/heap 包的基本步骤：

1. 定义一个结构体，该结构体用来表示堆中的元素。
2. 为该结构体实现 Len() int、Less(i, j int) bool 和 Swap(i, j int) 三个方法，这三个方法用来定义堆的行为。
3. 使用 heap.Init 方法初始化堆。
4. 使用 heap.Push 方法将元素加入堆中。
5. 使用 heap.Pop 方法移除并返回堆顶元素。

下面是一个简单的使用 container/heap 包的例子，实现了一个最小堆：

package main
 
import (
    "container/heap"
    "fmt"
)
 
// 定义一个结构体，用来表示堆中的元素
type IntHeap []int
 
// 实现 Len 方法
func (h IntHeap) Len() int           { return len(h) }
 
// 实现 Less 方法，定义堆是最小堆
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
 
// 实现 Swap 方法
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
// 实现 Push 方法，用于将元素加入堆中
func (h *IntHeap) Push(x interface{}) {
    // Push 方法接受 interface{} 类型的参数，因此需要类型断言
    *h = append(*h, x.(int))
}
 
// 实现 Pop 方法，用于移除堆顶元素
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}
 
func main() {
    // 创建一个 IntHeap 实例
    h := &IntHeap{1, 5, 2}
 
    // 初始化堆
    heap.Init(h)
 
    // 加入新元素
    heap.Push(h, 3)
    heap.Push(h, 4)
 
    // 输出堆顶元素，并移除它
    for h.Len() > 0 {
        fmt.Printf("head: %d\n", heap.Pop(h))
    }
}

这个例子中定义了一个整数类型的最小堆，并演示了如何初始化、添加元素、获取堆顶元素以及移除堆顶元素。