Go语言在测距时移除优先级队列中的元素的安全方法

envsm3lx 于 11个月前发布在 Go

关注(0)|答案(3)|浏览(137)

我从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

来源：https://stackoverflow.com/questions/49173773/safe-way-of-removing-elements-in-priority-queue-while-ranging

3条答案

按热度按时间

bttbmeg01#

每次调用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

赞(0）回复(0）举报 11个月前

wztqucjr2#

我认为你没有使用正确的数据结构或者使用的数据结构不正确。队列的概念是把项目放在最后以供将来处理，并从开始处理它们。
如果您不想处理某些项目，您可以在排队之前对其进行筛选，或者在处理之前从队列中取出它们时对其进行筛选。

赞(0）回复(0）举报 11个月前

im9ewurl3#

假设我有一个PriorityQueue结构，它 Package 了container/heap调用，并包含一个实现heap.Interface的queue

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-allocating

赞(0）回复(0）举报 11个月前

我来回答

Go语言在测距时移除优先级队列中的元素的安全方法

3条答案

相关问题

热门标签

最新问答

Go语言 在测距时移除优先级队列中的元素的安全方法

3条答案

相关问题

热门标签

最新问答

Go语言在测距时移除优先级队列中的元素的安全方法