概述
包 heap 为所有实现了 heap.Interface 的类型提供堆操作。 一个堆即是一棵树, 这棵树的每个节点的值都比它的子节点的值要小, 而整棵树最小的值位于树根(root), 也即是索引 0 的位置上。
堆是实现优先队列的一种常见方法。 为了构建优先队列, 用户在实现堆接口时, 需要让 Less() 方法返回逆序的结果, 这样就可以在使用 Push 添加元素的同时, 通过 Pop 移除队列中优先级最高的元素了。 具体的实现请看接下来展示的优先队列例子。
// 这段代码演示了如何使用堆接口构建一个整数堆。 package main import ( "container/heap" "fmt" ) // IntHeap 是一个由整数组成的最小堆。 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 和 Pop 使用 pointer receiver 作为参数, // 因为它们不仅会对切片的内容进行调整,还会修改切片的长度。 *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 } // 这个示例会将一些整数插入到堆里面, 接着检查堆中的最小值, // 之后按顺序从堆里面移除各个整数。 func main() { h := &IntHeap{2, 1, 5} heap.Init(h) heap.Push(h, 3) fmt.Printf("minimum: %d ", (*h)[0]) for h.Len() > 0 { fmt.Printf("%d ", heap.Pop(h)) } }
minimum: 1 1 2 3 5
// 这段代码演示了如何使用堆接口构建一个优先队列。 package main import ( "container/heap" "fmt" ) // Item 是优先队列中包含的元素。 type Item struct { value string // 元素的值,可以是任意字符串。 priority int // 元素在队列中的优先级。 // 元素的索引可以用于更新操作,它由 heap.Interface 定义的方法维护。 index int // 元素在堆中的索引。 } // 一个实现了 heap.Interface 接口的优先队列,队列中包含任意多个 Item 结构。 type PriorityQueue []*Item func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { // 我们希望 Pop 返回的是最大值而不是最小值, // 因此这里使用大于号进行对比。 return pq[i].priority > pq[j].priority } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) item := x.(*Item) item.index = n *pq = append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] item.index = -1 // 为了安全性考虑而做的设置 *pq = old[0 : n-1] return item } // 更新函数会修改队列中指定元素的优先级以及值。 func (pq *PriorityQueue) update(item *Item, value string, priority int) { item.value = value item.priority = priority heap.Fix(pq, item.index) } // 这个示例首先会创建一个优先队列,并在队列中包含一些元素 // 接着将一个新元素添加到队列里面,并对其进行操作 // 最后按优先级有序地移除队列中的各个元素。 func main() { // 一些元素以及它们的优先级。 items := map[string]int{ "banana": 3, "apple": 2, "pear": 4, } // 创建一个优先队列,并将上述元素放入到队列里面, // 然后对队列进行初始化以满足优先队列(堆)的不变性。 pq := make(PriorityQueue, len(items)) i := 0 for value, priority := range items { pq[i] = &Item{ value: value, priority: priority, index: i, } i++ } heap.Init(&pq) // 插入一个新元素,然后修改它的优先级。 item := &Item{ value: "orange", priority: 1, } heap.Push(&pq, item) pq.update(item, item.value, 5) // 以降序形式取出并打印队列中的所有元素。 for pq.Len() > 0 { item := heap.Pop(&pq).(*Item) fmt.Printf("%.2d:%s ", item.priority, item.value) } }
05:orange 04:pear 03:banana 02:apple