谁能给我解释一下: 我想在GO中实现一个优先级队列(接口实现取自link,但优先级最低)
我的代码:
pq := make(PriorityQueue, 0)
pq.Push(&Item{value: 0, priority: 0})
heap.Init(&pq)
fmt.Println(heap.Pop(&pq).(*Item))
item := &Item{value: 1, priority: 10}
pq.Push(item)
item = &Item{value: 2, priority: 20}
pq.Push(item)
item = &Item{value: 3, priority: 5}
pq.Push(item)
fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))
// Output:
&{0 0 -1}
&{1 10 -1}
&{3 5 -1}
&{2 20 -1}
为什么不输出:
&{0 0 -1}
&{3 5 -1}
...
TLDR使用heap.Push(...)
和heap.Pop(...)
在您的队列中添加和删除并保持秩序。
问题出在您的设置中。您不应该直接从您的队列中推入或弹出,并期望它被订购。调用heap.Init(&pq)
将对整个堆进行排序,因此您可以一次加载所有内容并对所有内容进行排序。
对于您的用例,您应该使用堆实用程序进行推送和弹出。添加到队列时,请使用heap.Push(...)
而不是pq.Push(...)
pq := make(PriorityQueue, 0)
heap.Push(&pq, &Item{value: "0", priority: 0, index: 0})
item := &Item{value: "1", priority: 10, index: 1}
heap.Push(&pq, item)
item = &Item{value: "2", priority: 20, index: 2}
heap.Push(&pq, item)
item = &Item{value: "3", priority: 5, index: 3}
heap.Push(&pq, item)
fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))
后续推送和弹出将始终以此方式排序。因为每件商品都是在插入时订购的,所以您不需要调用heap.Init(&pq)
。这更接近于在推送和弹出点缀的生产环境中使用的实现。