在测距时删除优先级队列中元素的安全方法

Question

我从go文档中获取了优先级队列的完整实现。 如果元素满足某些条件，我想删除它们。所以我应该：

• 然后迭代队列
• 检查状况
• 如果条件满足，则删除元素

像这样：

for i, value := range pq{
  if someCondtion{
    heap.Remove(&pq, i)
  }

}

或者为了简单起见：

for i, value := range pq{
    heap.Remove(&pq, i)
}

但这不是安全的方法，因为有一个错误：

panic: runtime error: index out of range
goroutine 1 [running]:
main.PriorityQueue.Swap(...)
main.(*PriorityQueue).Swap(0xc420088020, 0x2, 0x0)
container/heap.Remove(0x4c69a0, 0xc420088020, 0x2, 0xf, 0x0)

我怎样才能正确地做到这一点？ 这是一个例子 https://play.golang.org/p/XrQdAJIbZPw

Answer 1

每次调用

heap.Remove

后，堆都会重新组织。因此

pq

的初始长度在每次循环中都会变小。当它小于

i

所要求的当前值时，您就会到达该点。

如果您操作

pq

，您必须像示例中那样进行循环：

for pq.Len() > 0 {
    item := heap.Pop(&pq).(*Item)
    fmt.Printf("%.2d:%s\n", item.priority, item.value)
}

参见https://play.golang.org/p/Ayt4_zLo8FF

Answer 2

我认为您没有使用正确的数据结构或使用的数据结构不正确。队列的想法是将项目放在末尾以供将来处理，并从开头取出项目来处理它们。

如果您不想处理某些项目，您可以在排队之前对其进行过滤，或者在处理之前从队列中取出它们时进行过滤。

Answer 3

假设我有一个

PriorityQueue

结构体，它包装

container/heap

调用并包含一个实现

queue

 的 

heap.Interface

func (pq *PriorityQueue[T]) Remove(shouldRemove func(T) bool) {
    tmpQueue := pq.queue[:0]
    for _, element := range pq.queue{
        if !shouldRemove(element) {
            tmpQueue = append(tmpQueue, element)
        }
    }
    // clear the rest of the queue to avoid memory leaks
    var zero T
    for i := len(tmpQueue); i < len(pq.queue); i++ {
        pq.queue[i] = zero
    }
    pq.queue= tmpQueue
    // re-heapify the queue
    heap.Init(pq.queue)
}

过滤代码来自：https://github.com/golang/go/wiki/SliceTricks#filtering-without-allocing