Go 优先队列的实现

优先队列的构造主要使用”container/heap”包下的heap来实现

看先heap.Interface的定义

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

首先要实现 sort.Interface 接口的三个方法

type Interface interface {
        // 获取数据集合元素个数
        Len() int
        // 如果 i 索引的数据小于 j 索引的数据，返回 true，且不会调用下面的 Swap()，即数据升序排序。
        Less(i, j int) bool
        // 交换 i 和 j 索引的两个元素的位置
        Swap(i, j int)
}

接着实现heap.Interface中的Pop和Push两个方法：

func Push(h Interface, x interface{}) {
}
func Pop(h Interface) interface{} {
}

调用heap的push和pop方法即可：

//heap文件中已定义的方法
func Push(h Interface, x interface{}) {
    h.Push(x)
    up(h, h.Len()-1)
}
//
func up(h Interface, j int) {
    for {
        i := (j - 1) / 2 // parent
        if i == j || !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        j = i
    }
}
//可以看到，需要使用到我们定义的一些less函数

举例：

//sort.IntSlice已经实现了 sort.Interface的三个方法
type hp struct {
    sort.IntSlice
}

//优先队列需要实现 Push和Pop两个方法
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
    a := h.IntSlice
    v := a[len(a)-1]
    h.IntSlice = a[:len(a)-1]
    return v
}
//
func main(){
  h := hp{}
    heap.Push(&h, 2)
    heap.Push(&h, 1)
    fmt.Println(h)
  //打印出来是已经排序好的
}