我正在尝试根据文档中提供的示例实现优先级队列。文件: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文件中:
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)) } }
如您所见,在与示例进行比较时,我不使用指针,因为这样做会给我一个编译错误,告诉我我的优先级队列未正确实现接口。
这会给我带来以下问题:
heap.Push(q, item)
该项目未附加到队列中。
我试图写出队列指针地址,它显示了不同的地址。这就解释了为什么它不起作用,但是切片不是地图长的引用类型吗?
更具体地说:如何解决我的问题?
希望能对您有所帮助!
编辑:添加了完整的代码和错误:不能将q(类型pq.PriorityQueue)用作堆类型。函数参数中的接口:pq.PriorityQueue没有实现堆。接口(Pop方法具有指针接收器)
如示例代码所示,该Push方法必须具有指针接收器。
Push
诀窍是所有对heap.XXX函数的调用都要求您将堆作为指针传递(例如:)heap.Init(&pq)。在您发布的代码中情况并非如此。这是您的代码的有效版本。您可以在Go操场上运行它。
heap.XXX
heap.Init(&pq)
请注意,在这段代码中,我明确地将队列初始化为指针:q := new(PriorityQueue)。这就是我传递给所有heap功能的东西。
q := new(PriorityQueue)
heap
之所以引起这种混乱,主要是因为您实际上要实现2个接口。的heap.Interface和sort.Interface(后者是现有的类型定义的一部分)。但是sort接口对于非指针接收器来说是很好的,而另一个接口则不是。
heap.Interface
sort.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 }