go - 从golang中的优先级队列中删除元素

Question

我从golang docs中获取优先级队列的完整实现.我对一次删除多个元素很感兴趣，例如 heap.Remove(&queue, index1, index2, ...)。

现在可以用直接的方式完成:

for _, event := range events {
    heap.Remove(&queue, event.getIndex())
}

但此方法有开销，因为每次调用 heap.Remove 都会重新组织树。如果我们可以先删除所有不需要的元素，然后再重新组织树，似乎效率更高。

如何实现？

Answer 1

由于堆的底层数据结构是 slice ，您可以直接从 slice 中删除元素，然后重新初始化堆。

从你的例子开始:

for _, event := range events {
    i := event.GetIndex()
    queue[i], queue[len(queue)-1] = queue[len(queue)-1], queue[i]
    queue = queue[:len(queue)-1]
}
heap.Init(&queue)

还有一个工作示例:https://play.golang.org/p/-KMEilCm3t9

func main() {
    h := IntHeap{1, 5, 2, 9, 8, 3, 7}

    toRemove := 8
    for i := 0; i < len(h); i++ {
        n := h[i]
        if n == toRemove {
            h[i], h[len(h)-1] = h[len(h)-1], h[i]
            h = h[:len(h)-1]
            i--
        }
    }

    heap.Init(&h)
    fmt.Println(h)
}