golang中container/heap包 golang中container

【golang中container/heap包】任何实现了 heap.Interface 接口的对象都可以使用heap包提供的方法对堆进行操作（堆是一个完成二叉树）。通过对heap.Interface 中的 Less 方法的不同实现，来实现最大堆和最小堆。通常堆的数据结构是一个一维数组。
heap包提供的函数列表：
1）func Init(h Interface)
2）func Pop(h Interface) interface{}
3）func Push(h Interface, x interface{})
4）func Remove(h Interface, i int) interface{}
5）type Interface
现在对提供的函数进行分析：

func Init(h Interface) 参数列表：h，实现了heap.Interface接口的堆对象功能说明：在对堆h进行操作前必须保证堆已经初始化（即符合堆结构），该方法可以在堆中元素的顺序不符合堆要求时调用，调用后堆会调整为标准的堆结构，该方法的时间复杂度为：O(n)，n为堆h中元素的总个数。

前面有一个实现了heap.Interface 接口的对象？那么实现了这个接口的对象要实现哪些内容呢？

一共需要实现5个方法，Len、Swap、Less、Pop、Push标准库源码： type Interface interface { sort.Interface Push(x interface{}) Pop() interface{} } 功能：这是堆的接口，heap包里面的方法只是提供的一些堆算法操作，要想使用这些算法操作，就必须实现这些接口，每个接口方法都有具体的含义，堆本身的数据结构由这个接口的具体实现决定，可以是数组、列表。接口方法： 1）sort.Interface 要实现三个接口：func Len() int，func Less(i, j int) bool，func Swap(i, j int)，其中Less方法的实现决定了堆是最大堆还是最小堆。 type myHeap []int// 定义一个堆，存储结构为数组// 最小堆的Less方法实现 func (h *myHeap) Less(i, j int) bool { return (*h)[i] < (*h)[j] }// 最大堆的Less方法实现 func (h *myHeap) Less(i, j int) bool { return (*h)[i] > (*h)[j] }2）Push(x interface{}) 参数列表：x将存到堆中的元素功能说明：把元素x存放到切片最末尾。 func (h *myHeap) Push(v interface{}) { *h = append(*h, v.(int)) }3）Pop() interface{} 返回值：移除切片末尾的那个元素功能说明：把最后一个元素移除并将其值返回。 func (h *myHeap) Pop() (v interface{}) { *h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1] return }

编写一个应用heap包的案例：

package mainimport ( "fmt" "container/heap" )type myHeap []int/* 实现排序 */ func (h *myHeap) Len() int { return len(*h) }func (h *myHeap) Swap(i, j int) { (*h)[i], (*h)[j] = (*h)[j], (*h)[i] }// 最小堆实现 func (h *myHeap) Less(i, j int) bool { return (*h)[i] < (*h)[j] }/* 实现往堆中添加元素 */ func (h *myHeap)Push(v interface{}) { *h = append(*h, v.(int)) }/* 实现删除堆中元素 */ func (h *myHeap)Pop() (v interface{}) { *h, v = (*h)[:len(*h)-1], (*h)[len(*h)-1] return }// 按层来遍历和打印堆数据，第一行只有一个元素，即堆顶元素 func (h myHeap) printHeap() { n := 1 levelCount := 1 for n <= h.Len() { fmt.Println(h[n-1 : n-1+levelCount]) n += levelCount levelCount *= 2 } }func main() { data := [7]int{13,12,45,23,11,9,20} aHeap := new(myHeap) for i := 0; i < len(data); i++ { aHeap.Push(data[i]) } aHeap.printHeap()// 堆排序处理 heap.Init(aHeap) aHeap.printHeap() }