CODEWITHSUNDEEP
goheappriority-queue
Kenenbek Arzymatov
Kenenbek Arzymatov

Reputation: 9119

Remove elements from priority queue in golang

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?

Upvotes: 2

Views: 3200

Answers (2)

Mr_Pink
Mr_Pink

Reputation: 109406

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)
}

Upvotes: 3

thisischuck
thisischuck

Reputation: 163

In order to answer this question we first need to understand what a heap is. Heaps are a data structure that allow us to find the largest or smallest value depending on whether it is a Min Heap or a Max Heap. To do this quickly, the computer maintains a tree, this image sums it up quite well. This is a max heap:

Max-heap diagram, nine nodes

Of course computer's memory aren't laid out in trees, they are laid out linearly. In fact, go stores heaps in slices, which means that you can iterate through the slice and remove elements like you'd normally do, for example:

  for i:=0; i<len(heap); i++ {  
    for _, element := heap {
      if element == to_remove {
        heap = append(heap[:i], heap[i+1:])
        i--
      }
    }
  }

Upvotes: 1

Related Questions