CODEWITHSUNDEEP
goheappriority-queue
Kenenbek Arzymatov
Kenenbek Arzymatov

Reputation: 9119

Safe way of removing elements in priority queue while ranging

I took the full implementation of priority queue from go documentation. I want to remove elements if they satisfy some condition. So I should:

Like this:

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

}

Or for simplicity:

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

But it is not the safe way because there is an error:

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)

How can I properly do it? Here is an example https://play.golang.org/p/XrQdAJIbZPw

Upvotes: 1

Views: 885

Answers (3)

ahmedakef
ahmedakef

Reputation: 301

assuming I have a PriorityQueue struct the wraps the container/heap calls and contain a queue which implements 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)
}

the filtering code comes from: https://github.com/golang/go/wiki/SliceTricks#filtering-without-allocating

Upvotes: 0

mbuechmann
mbuechmann

Reputation: 5770

I think you are not using the correct data structure or the used data structure not correctly. The idea of a queue is to put items at the end for future processing and to take items from the beginning to process them.

If you do not want to process certain items, you could either filter them before queuing or filter when they are taken from the queue before processing.

Upvotes: 3

user9455968
user9455968

Reputation:

After every call to heap.Remove the heap is reorganized. So the initial length of pq gets smaller in every loop. You will reach the point when it is smaller than the current value of i requires it to be.

If you manipulate pq you must loop as it is done in the example:

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

see https://play.golang.org/p/Ayt4_zLo8FF

Upvotes: 3

Related Questions