www.zhblog.net

heap 包


如果在收集元素的过程中,想要一并排序,方式之一是使用堆排序,对于这个需求,Go 提供了heap包作为实现上的辅助。

heap包提供的是最小堆树演算,底层的数据结构必须实现heap.Interface

type Interface interface {
    sort.Interface
    Push(x interface{}) 
    Pop() interface{} 
}

也就是说,除了实现sort.InterfaceLenLessSwap方法之外,还要实现PushPop的行为,在heap的 Go 官方文件说明有个简单范例:

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

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

实现了heap.Interface的数据结构,就可以透过heap包中的InitPushPop等函数来进行操作:

h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("minimum: %d\n", (*h)[0])
for h.Len() > 0 {
    fmt.Printf("%d ", heap.Pop(h))
}

PushPop过程中有关堆树的调整,就都由heap.Pushheap.Pop等函数来处理了。

官方文件提供的范例是可以简单示范heap包的使用,不过,一下子使用heap.Xxx,一下子又是使用h.Xxx的混合风格,看来蛮怪的,可以来改变一下:

package main

import (
    "container/heap"
    "fmt"
)

// IntSlice 实现了 heap.Interface
type IntSlice []int

func (s IntSlice) Len() int           { return len(s) }
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s IntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func (s *IntSlice) Push(x interface{}) {
    *s = append(*s, x.(int))
}

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

// IntHeap 封装了 IntSlice
type IntHeap struct {
    elems IntSlice
}

// 实现相关函数或方法时,透过 heap 提供的函数
func NewIntHeap(numbers ...int) *IntHeap {
    h := &IntHeap{IntSlice(numbers)}
    heap.Init(&(h.elems))
    return h
}

func (h *IntHeap) Push(n int) {
    heap.Push(&(h.elems), n)
}

func (h *IntHeap) Pop() int {
    return heap.Pop(&(h.elems)).(int)
}

func (h *IntHeap) Len() int {
    return len(h.elems)
}

// 一律透过 h 来操作
func main() {
    h := NewIntHeap(2, 1, 5)
    h.Push(3)
    for h.Len() > 0 {
        fmt.Printf("%d ", h.Pop())
    }
}

官方文件提供的范例中,还有个PriorityQueue的实现,类似地,该范例是简单示范,混合了两种操作风格,你也可以试着自行把heap.Xxx的操作给封装起来。


展开阅读全文

评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 心情