英文:
What's wrong with my Priority Queue's Pop method?
问题
根据Rob Pike的负载均衡器演示，我实现了自己的优先队列，但我的Pop方法不正确，有人能告诉我错在哪里吗？
package main
import (
"fmt"
"container/heap"
)
type ClassRecord struct {
name string
grade int
}
type RecordHeap []*ClassRecord
func (p RecordHeap) Len() int { return len(p) }
func (p RecordHeap) Less(i, j int) bool {
return p[i].grade < p[j].grade
}
func (p *RecordHeap) Swap(i, j int) {
a := *p
a[i], a[j] = a[j], a[i]
}
func (p *RecordHeap) Push(x interface{}) {
a := *p
n := len(a)
a = a[0 : n+1]
r := x.(*ClassRecord)
a[n] = r
*p = a
}
func (p *RecordHeap) Pop() interface{} {
a := *p
*p = a[0 : len(a)-1]
r := a[len(a)-1]
return r
}
func main() {
a := make([]ClassRecord, 6)
a[0] = ClassRecord{"John", 80}
a[1] = ClassRecord{"Dan", 85}
a[2] = ClassRecord{"Aron", 90}
a[3] = ClassRecord{"Mark", 65}
a[4] = ClassRecord{"Rob", 99}
a[5] = ClassRecord{"Brian", 78}
h := make(RecordHeap, 0, 100)
for _, c := range a {
fmt.Println(c)
heap.Push(&h, &c)
fmt.Println("Push: heap has", h.Len(), "items")
}
for i, x := 0, heap.Pop(&h).(*ClassRecord); i < 10 && x != nil; i++ {
fmt.Println("Pop: heap has", h.Len(), "items")
fmt.Println(*x)
}
}
**编辑：**除了cthomo06指出的方法之外，另一种修复方法是创建一个指针数组，如下所示，
a := make([]*ClassRecord, 6)
a[0] = &ClassRecord{"John", 80}
a[1] = &ClassRecord{"Dan", 85}
......
英文:
Based on Rob Pike's load balancer demo, I implemented my own priority queue, but my Pop method is not right, can anyone tell me what's wrong?
package main
import (
"fmt"
"container/heap"
)
type ClassRecord struct {
name string
grade int
}
type RecordHeap []*ClassRecord
func (p RecordHeap) Len() int { return len(p) }
func (p RecordHeap) Less(i, j int) bool {
return p[i].grade < p[j].grade
}
func (p *RecordHeap) Swap(i, j int) {
a := *p
a[i], a[j] = a[j], a[i]
}
func (p *RecordHeap) Push(x interface{}) {
a := *p
n := len(a)
a = a[0 : n+1]
r := x.(*ClassRecord)
a[n] = r
*p = a
}
func (p *RecordHeap) Pop() interface{} {
a := *p
*p = a[0 : len(a)-1]
r := a[len(a)-1]
return r
}
func main() {
a := make([]ClassRecord, 6)
a[0] = ClassRecord{"John", 80}
a[1] = ClassRecord{"Dan", 85}
a[2] = ClassRecord{"Aron", 90}
a[3] = ClassRecord{"Mark", 65}
a[4] = ClassRecord{"Rob", 99}
a[5] = ClassRecord{"Brian", 78}
h := make(RecordHeap, 0, 100)
for _, c := range a {
fmt.Println(c)
heap.Push(&h, &c)
fmt.Println("Push: heap has", h.Len(), "items")
}
for i, x := 0, heap.Pop(&h).(*ClassRecord); i < 10 && x != nil; i++ {
fmt.Println("Pop: heap has", h.Len(), "items")
fmt.Println(*x)
}
}
EDIT: besides the way cthom06 pointed out, another way to fix this is to create a pointer array as follows,
a := make([]*ClassRecord, 6)
a[0] = &ClassRecord{"John", 80}
a[1] = &ClassRecord{"Dan", 85}
......
答案1
得分: 1
编辑：
哦，我应该立刻看到这个问题。
heap.Push(&h, &c)
你推送了c的地址，在每次迭代range时都会被重用。堆中的每个记录都是指向内存中相同区域的指针，最终会变成Brian。我不确定这是否是预期行为还是编译器的错误，但是
t := c
heap.Push(&h, &t)
可以解决这个问题。
另外：你的for循环有问题。
for h.Len() > 0 {
x := heap.Pop(&h...
应该修复它。
英文:
EDIT:
Oh I should've seen this right away.
heap.Push(&h, &c)
You push the address of c, which gets reused on each iteration of range. Every record in the heap is a pointer to the same area in memory, which ends up being Brian. I'm not sure if this is intended behavior or a compiler bug, but
t := c
heap.Push(&h, &t)
works around it.
Also: Your for loop is wrong.
for h.Len() > 0 {
x := heap.Pop(&h...
should fix it.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论