Change priority of items in a priority queue

Question

Using Scala 2.9 to implement a kind of Dijkstra algorithm (pseudo code)

val queue = new PriorityQueue
queue.insert(...)
while (!queue.isEmpty) {
  val u = queue.extractMin
  queue.foreach { v =>
    if (condition(u, v))
      queue.decreaseKey(v, newPriority)
  }
}

I'd like to change priority of an item in Scala's collection.mutable.PriorityQueue.

Therefore tried to

• remove item
• change priority
• reinsert into queue.

But I can't find a method to either update priority or remove a specific item (not necessarily head element) like java.util.PriorityQueue#remove(Object) as apposed in Removing an item from a priority queue.

• How this task can be done with scala.collection.mutable.PriorityQueue or do I have to use java.util.PriorityQueue instead?

• Does anyone know whether lack of such a method is by design and it would be recommended to rebuild the queue after changing priority of some items (maybe take a look at discussion about Priority queue with dynamic item priorities)?

Answer 1

Defining a case class for the PriorityQueue type to use with var for priority allows you to find it and mutate the priority. The PriorityQueue then has this new value. To get the ordering correct I had to clone it which reorders/forces the ordering. There might be a better way to do this without cloning.

case class Elem(var priority: Int, i: Int)

def MyOrdering = new Ordering[Elem] {
  def compare(a : Elem, b : Elem) = a.priority.compare(b.priority)
}

val pq = new scala.collection.mutable.PriorityQueue[Elem]()(MyOrdering)  ++ List(Elem(1,1), Elem(0,0), Elem(2,2))

pq.find(x => x.priority == 0) match {
  case Some(elem: Elem) => elem.priority = 3
  case None => println("Not found")
}

val pq2 = pq.clone
println(pq2)
println(pq2.dequeue)
println(pq2.dequeue)
println(pq2.dequeue)



:load SO.scala
Loading SO.scala...
defined class Elem
PileOrdering: java.lang.Object with Ordering[Elem]
pq: scala.collection.mutable.PriorityQueue[Elem] = PriorityQueue(Elem(2,2), Elem(0,0), Elem(1,1))
pq2: scala.collection.mutable.PriorityQueue[Elem] = PriorityQueue(Elem(3,0), Elem(2,2), Elem(1,1))
PriorityQueue(Elem(3,0), Elem(2,2), Elem(1,1))
Elem(3,0)
Elem(2,2)
Elem(1,1)

Answer 2

Priority queues are commonly implemented with heaps. Binary heaps are commonly implemented using arrays, and if the element you want to remove is not on the path between the root of the heap and its last element in the array ordering, then there is no obvious way to remove it. I assume that this is why Scala doesn't offer removal of arbitrary elements. However, if you implement your own heap, it's easy enough to implement decrease-key for a binary (min-)heap: you just compare the new priority for a node N to its parent's priority, and if necessary exchange the two. Do this repeatedly until N is at the top or N's parent has lower priority than N itself.