优先队列和堆 [英] Priority queue and heap
问题描述
我正在尝试根据文档中提供的示例实现优先级队列。
文档： priorityQueue
简而言之，它看起来像这样（不包括所有内容）：
package pq
类型项目结构{
容器接口{}
优先级int
索引int
}
类型PriorityQueue [] *项
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\\\
，& 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（\\\
Adr：％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）
该项未附加到队列。 p>
我试图写出队列指针地址，并显示不同的地址。这解释了为什么它不起作用，但是不能使用地图长时间不使用引用类型？
更具体地说：我如何解决我的问题？ p>
希望你可以帮助！
编辑：添加完整的代码和错误：不能使用q（键入pq.PriorityQueue）作为类型heap.Interface在函数参数中：
pq.PriorityQueue不实现heap.Interface（Pop方法有指针接收器）
如示例代码所示， Push 方法必须有一个指针接收器。
诀窍是所有对 heap.XXX 函数的调用，要求您以一个指针的形式传递堆（例如： heap.Init（& pq） ）。在您发布的代码中不是这样。这是您的代码的工作版本。您可以在 Go playground 上运行。
注意，在这段代码中，我明确地将队列初始化为一个指针：
q：= new（PriorityQueue）。这是我传递给所有的堆函数。 这里的混乱主要是因为你本质上实现2个接口
heap.Interface 和 sort.Interface （后者是之前的类型定义的一部分） 。但是非接收器的排序界面很好，而另一个则不是。
package main
importfmt
importcontainer / heap
func main（）{
q：= new（PriorityQueue）
heap。 Init（q）
fmt.Printf（\\\
Adr：％p\\\
，& 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））
}
}
类型项目结构{
容器接口{}
优先级int
索引int
}
类型PriorityQueue [] *项
func NewItem（值接口{}，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\\\
，pq）
n：= len（* pq）
item：= x。
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
}
I'm trying to implement a priority queue based on the example provided in the documentation. Docs: priorityQueue
In short it looks like this (not everything is included):
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
}
The main.go file:
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))
}
}
As you can see when comparing to the example I do not use pointers since doing that will give me a compile error telling me that my priority queue does not implement the interface properly.
This leaves me with the following problem when I do:
heap.Push(q, item)
that the item is not appended to the queue.
I've tried to write out the queues pointer address and it shows different addresses. This explains why it does not work, but souldn't slices not be reference types a long with maps?
And more specificly: How do i solve my problem?
Hope you can help!
Edit: Added full code and error: cannot use q (type pq.PriorityQueue) as type heap.Interface in function argument: pq.PriorityQueue does not implement heap.Interface (Pop method has pointer receiver)
As the example code shows, the Push method must have a pointer receiver.
The trick is that all the calls to heap.XXX functions, require that you pass your heap in as a pointer (e.g.: heap.Init(&pq)). This is not the case in the code you posted. Here is a working version of your code. You can run it on the Go playground.
Note that in this code, I explicitly initialize the queue as a pointer: q := new(PriorityQueue). And this is what I pass in to all the heap functions.
The confusion here arises mostly because you are essentially implementing 2 interfaces.
The heap.Interface and the sort.Interface (The latter is part of the prior's type definition). But the sort interface is fine with non-pointer receivers, while the other one is not.
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
}
这篇关于优先队列和堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
