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存放到切片最末尾。
type (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 main

import (
    "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()
}