【Go - 小顶堆/大顶堆】
在 Go 语言中，标准库 container/heap 提供了堆（Heap）的实现。可以使用 container/heap 包来实现自己的大顶堆或小顶堆。
小顶堆示例
以下是一个使用 container/heap 包实现的小顶堆示例：
package main
import (
"container/heap"
"fmt"
)
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i int, j int) bool {
return h[i] < h[j]
}
func (h IntHeap) Swap(i int, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0:n-1]
return x
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func main() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
m := (*h)[0]
fmt.Printf("minimum: %d\n", m)
m = heap.Pop(h).(int)
fmt.Printf("minimum %d\n", m)
m = heap.Pop(h).(int)
fmt.Printf("minimum %d\n", m)
}
注意📢 ：
- 涉及到空间变化的，Push，Pop 传参是指针类型，其余的是引用类型。
- Push，Pop的参数为interface{}，在内部再进行类型转换
大顶堆，则只需将Less函数改下，小于改为大于，其余代码一致。
func (h IntHeap) Less(i int, j int) bool {
return h[i] > h[j]
}