我正在尝试根据文档中提供的示例实现优先级队列。 文档:priorityQueue

简而言之，它看起来像这样(并不是所有的都包括在内):

    package pq

    type Item struct {
        container interface{}
        priority  int
        index     int
    }

    type PriorityQueue []*Item

    func NewItem(value interface{}, prio int) *Item {
        return &Item {container: value, priority: prio}
    }

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq *PriorityQueue) Swap(i, j int) {
    (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
    (*pq)[i].index = i
    (*pq)[j].index = j
}

    func (pq PriorityQueue) Push(x interface{}) {
        fmt.Printf("adr: %p\n", &pq)
        n := len(pq)
        item := x.(*Item)
        item.index = n
        pq = append(pq, item)
    }

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    itm := old[n - 1]
    itm.index = -1
    *pq = old[0 : n-1]
    return itm.container
}

main.go 文件:

func main() {
    q := pq.PriorityQueue{}
    heap.Init(q)
    fmt.Printf("\nAdr: %p\n", &q)
    q.Push(pq.NewItem("h", 2))

    for i := 0; i < 5; i++ {
        item := pq.NewItem("test", i * 13 % 7)
        heap.Push(q, item)
    }

    for q.Len() > 0 {
        fmt.Println("Item: " + heap.Pop(q).(string))
    }
}

正如您在与示例进行比较时看到的那样，我没有使用指针，因为这样做会给我一个编译错误，告诉我我的优先级队列没有正确实现接口(interface)。

这给我留下了以下问题:

heap.Push(q, item)

该项目未附加到队列中。

我试图写出队列指针地址，但它显示了不同的地址。这解释了为什么它不起作用，但是 slice 不应该是引用类型和 maps 吗？

更具体地说:我该如何解决我的问题？

希望你能帮上忙!

编辑:添加完整代码和错误:不能在函数参数中使用 q(类型 pq.PriorityQueue)作为类型 heap.Interface: pq.PriorityQueue没有实现heap.Interface(Pop方法有指针接收者)

最佳答案

如示例代码所示，Push 方法必须有一个指针接收器。

诀窍是所有对 heap.XXX 函数的调用都要求您将堆作为指针传递(例如:heap.Init(&pq)) .您发布的代码不是这种情况。这是您的代码的工作版本。您可以在 Go playground 上运行它.

请注意，在这段代码中，我明确地将队列初始化为一个指针:q := new(PriorityQueue)。这就是我传递给所有 heap 函数的内容。

这里的混淆主要是因为您实际上是在实现 2 个接口(interface)。 heap.Interface 和 sort.Interface(后者是先前类型定义的一部分)。但是排序接口(interface)适用于非指针接收器，而另一个则不行。

package main

import "fmt"
import "container/heap"

func main() {
    q := new(PriorityQueue)

    heap.Init(q)

    fmt.Printf("\nAdr: %p\n", &q)
    q.Push(NewItem("h", 2))

    for i := 0; i < 5; i++ {
        heap.Push(q, NewItem("test", i*13%7))
    }

    for q.Len() > 0 {
        fmt.Println("Item: " + heap.Pop(q).(string))
    }
}

type Item struct {
    container interface{}
    priority  int
    index     int
}

type PriorityQueue []*Item

func NewItem(value interface{}, prio int) *Item {
    return &Item{container: value, priority: prio}
}

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    fmt.Printf("adr: %p\n", pq)
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    itm := old[n-1]
    itm.index = -1
    *pq = old[0 : n-1]
    return itm.container
}

关于data-structures - 优先队列和堆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22543025/