Question

使用 container/heap

在这一小节中，你将了解 container/heap 包中提供的功能。首先，你应该知道的是 container/heap 实现的堆是一个树结构，树上的每个节点都是其所在子树上最小的元素。注意，我这里说的是最小的元素而不是最小的值是为了突出堆不止支持数值。

不过你可能已经猜到了，为了使用 Go 语言实现堆积树，你需要自己开发一种用来比较两个元素大小的方法。这种情况下，使用 Go 语言中的接口来定义比较合适。

这意味着 container/heap 包比 container 包中的其他两个包更加先进，而且你需要先完成一些定义之后才能使用 container/heap 包的功能。更准确地说，container/heap 包要求你实现 container/heap.Interface，其定义如下：

type Interface struct {
    sort.Interface
    Push(x interface{}) // 将 x 添加为第 Len() 个元素
    Pop() interface{}   // 删除并返回第 Len() - 1 个元素。
}

第 7 章“反射和接口”中会更详细地介绍接口。目前，你只用记住实现 Go 语言的接口只需要实现接口中的函数和其中组合的其他接口，比如上面的例子中的 sort.Interface、Push() 函数和 Pop() 函数。sort.Interface 中需要实现的函数包括 Len()、Less() 和 Swap()，实现这些函数很有必要，因为实现排序的功能必须要先实现交换两个元素、计算需要排序的对象的值以及根据前面计算的值判断两元素大小这些功能。尽管你可能认为这工作量很大，但大多数情况下这些函数的实现要么很琐碎，要么很简单。

由于这一节的目的是为了阐明 container/heap 的用法而不是为了让你头疼，例子中元素的数据类型都将使用 float32。

conHeap.go 中的 Go 语言代码将分为五个部分介绍。第一部分如下：

package main

import (
    "container/heap"
    "fmt"
)

type heapFloat32 []float32

conHeap.go 的第二部分是如下的 Go 代码：

func (n *heapFloat32) Pop() interface{} {
    old := *n
    x := old[len(old)-1]
    new := old[0 : len(old)-1]
    *n = new
    return x
}

func (n *heapFloat32) Push(x interface{}) {
    *n = append(*n, x.(float32))
}

尽管这里定义了 Pop() 和 Push() 这两个函数，但这只是为了遵循接口的要求。当你需要在堆中增删元素的时候还是应该分别调用 heap.Push() 和 heap.Pop()。

conHeap.go 的第三个代码段包含如下的 Go 代码：

func (n heapFloat32) Len() int {
    return len(n)
}

func (n heapFloat32) Less(a, b int) bool {
    return n[a] < n[b]
}

func (n heapFloat32) Swap(a, b int) {
    n[a], n[b] = n[b], n[a]
}

这一部分实现了 sort.Interface 接口所需要的三个函数。

conHeap.go 的第四部分如下：

func main() {
    myHeap := &heapFloat32{1.2, 2.1, 3.1, -100.1}
    heap.Init(myHeap)
    size := len(*myHeap)
    fmt.Printf("Heap size: %d\n", size)
    fmt.Printf("%v\n", myHeap)

conHeap.go 的最后一个代码段如下：

    myHeap.Push(float32(-100.2))
    myHeap.Push(float32(0.2))
    fmt.Printf("Heap size: %d\n", len(*myHeap))
    fmt.Printf("%v\n", myHeap)
    heap.Init(myHeap)
    fmt.Printf("%v\n", myHeap)
}

conHeap.go 的最后一部分中使用 heap.Push() 向 myHeap 中添加了两个新元素。然而，为了让堆重新有序排列，你需要再次调用 heap.Init()

执行 conHeap.go 将生成如下输出：

$ go run conHeap.go 
Heap size: 4
&[-100.1 1.2 3.1 2.1]
Heap size: 6
&[-100.1 1.2 3.1 2.1 -100.2 0.2]
&[-100.2 -100.1 0.2 2.1 1.2 3.1]

输出的最后一行中的 2.1 1.2 3.1 这三个数的顺序看上去有些不对，这是因为堆不是按照线性逻辑进行排序的。请记住，堆是一个树状结构，而不是像数组或切片这样的线性结构。