如何在Go中使用heap包？

Question

我一直试图在Go中使用Heap包，但我不确定如何初始化它。

package main
import "container/heap"

type PriorityMessage struct {
    Priority int
    Message string
}

func priorityQueue() {
    //WOULD THIS not initialize the heap?
    h := heap.Init(h PriorityMessage)

}

我一直试图在网上寻找其他人如何初始化他们的堆的例子，他们似乎每次都会创建自己版本的Go堆包。从堆包中调用heap.Init(h接口)函数会不起作用吗？

Answer 1

这是你应该首先实现的heap.Interface。

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

这意味着您应该拥有用于PriorityMessage结构的必要方法。将结构的实例传递到heap.Init(&pm)之后。

您可以在评论中链接的godoc中找到详细信息。

只是为了澄清混淆。Go是一种缺乏泛型的强类型语言。所以堆包设计的方式是它是类型独立的。您可以为要实现的所有类型创建自己的实现。任何实现heap.Interface的类型都可以被堆包使用。

Answer 2

  //https://cs.opensource.google/go/go/+/refs/tags/go1.16.6:src/container/heap/example_intheap_test.go 
    
    // This example demonstrates an integer heap built using the heap interface.
    //package heap_test
    
    import (
        "container/heap"
        "fmt"
    )
    
    // An IntHeap is a min-heap of ints.
    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{}) {
        // Push and Pop use pointer receivers because they modify the slice's length,
        // not just its contents.
        *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
    }
    
    // This example inserts several ints into an IntHeap, checks the minimum,
    // and removes them in order of priority.
    func Example_intHeap() {
        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))
        }
        // Output:
        // minimum: 1
        // 1 2 3 5
    }