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

Question

I take the full realization of priority queue from golang docs. I'm interesting in removing several elements at once like heap.Remove(&queue, index1, index2, ...).

Now it can be done in the straightforward way:

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

But this method has an overhead because every call to heap.Remove reorganizes tree. It seems more efficient if we can remove all unnecessary elements firstly and only then reorganize tree.

How it can be implemented?

Answer 1

Since the underlying data structure of your heap is a slice, you can remove the elements directly from the slice and re-initialize the heap again after.

Starting from your example:

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)

And a working example: 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)
}