05.9.1 使用 container/heap
在这一小节中,你将了解 container/heap
包中提供的功能。首先,你应该知道的是 container/heap
实现的堆是一个树结构,树上的每个节点都是其所在子树上最小的元素。注意,我这里说的是最小的元素而不是最小的值是为了突出堆不止支持数值。
不过你可能已经猜到了,为了使用 Go 语言实现堆积树,你需要自己开发一种用来比较两个元素大小的方法。这种情况下,使用 Go 语言中的接口来定义比较合适。
这意味着 container/heap
包比 container
包中的其他两个包更加先进,而且你需要先完成一些定义之后才能使用 container/heap
包的功能。更准确地说,container/heap
包要求你实现 container/heap.Interface
,其定义如下:
第 7 章“反射和接口”中会更详细地介绍接口。目前,你只用记住实现 Go 语言的接口只需要实现接口中的函数和其中组合的其他接口,比如上面的例子中的 sort.Interface
、Push()
函数和 Pop()
函数。sort.Interface
中需要实现的函数包括 Len()
、Less()
和 Swap()
,实现这些函数很有必要,因为实现排序的功能必须要先实现交换两个元素、计算需要排序的对象的值以及根据前面计算的值判断两元素大小这些功能。尽管你可能认为这工作量很大,但大多数情况下这些函数的实现要么很琐碎,要么很简单。
由于这一节的目的是为了阐明 container/heap
的用法而不是为了让你头疼,例子中元素的数据类型都将使用 float32
。
conHeap.go
中的 Go 语言代码将分为五个部分介绍。第一部分如下:
conHeap.go
的第二部分是如下的 Go 代码:
尽管这里定义了 Pop()
和 Push()
这两个函数,但这只是为了遵循接口的要求。当你需要在堆中增删元素的时候还是应该分别调用 heap.Push()
和 heap.Pop()
。
conHeap.go
的第三个代码段包含如下的 Go 代码:
这一部分实现了 sort.Interface
接口所需要的三个函数。
conHeap.go
的第四部分如下:
conHeap.go
的最后一个代码段如下:
conHeap.go
的最后一部分中使用 heap.Push()
向 myHeap
中添加了两个新元素。然而,为了让堆重新有序排列,你需要再次调用 heap.Init()
执行 conHeap.go
将生成如下输出:
输出的最后一行中的 2.1 1.2 3.1
这三个数的顺序看上去有些不对,这是因为堆不是按照线性逻辑进行排序的。请记住,堆是一个树状结构,而不是像数组或切片这样的线性结构。
Last updated