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.

Answer 3

I don't have experience with Scala but the problem I see is that a plain priority queue is not enough for Dijkstra since you need to know where a particular vertex is stored in the queue before you can do a decrease-key. In other words, a dictionary (hash table) is required to map vertex ids to indices within the heap in expected constant time. Then you get an overall O(log n) for the decrease-key. It seems unlikely to me that such a functionality can be found in a standard library. Writing a suitable class from scratch should be easy though.

The code at the end of this lecture explains the idea (but in python.. sorry).

Answer 4

Not a Scala user, but so far I've never seen a built-in/pre-made Heap implementation that allows for Decrease Key, because Decrease Key is only effective if you can provide (the location of) the element being DK'd.

The easiest way of getting the DK operation is to implement the Heap yourself. My method is usually to keep my Elements separate (in an unorganized array/vector/linked list) and to build a Heap of pointers-to-Elements (or array-indeces). Then, given a Heap node, you can look up the element by accessing it in the array (dereference or index-lookup). To support DK and/or Random Delete, you can add an additional variable to the Element that points to the Heap node (or keeps the index, if array-based Heap). This allows you to have O(1) access in either direction.

If your pre-made Heap comes with a DK operation that accepts a pointer to the Node, then you can simply build a Heap of self-made Node Objects, which simply wrap the Pointer in a class so you can provide comparison operators (required to build a Heap of them).

Answer 5

I have implemented a class to do exactly what you need:

• insert is enqueue
• extractMin is dequeue
• decreaseKey is putValue

---

import scala.annotation.tailrec
import scala.collection.mutable.{ArrayBuffer, Map}
import scala.util.Try

class HeapedMap[K, V] (implicit ord: Ordering[V]){
  val dict = Map[K,Int]() // Keeps index of key withing vector
  val vector = ArrayBuffer[(K,V)]()

  override def toString(): String = vector.toString
  def toMap(): scala.collection.immutable.Map[K,V] = dict.mapValues(vector(_)._2).toMap
  def toSeq(): Seq[(K,V)] = vector
  def toList(): List[(K,V)] = vector.toList

  private def parent(i: Int): Int = (i - 1) / 2
  private def right(i: Int): Int = (i * 2 + 1) + 1
  private def left(i: Int): Int = (i * 2 + 1)
  private def exists(i: Int): Boolean = Try(vector(i)).isSuccess
  private def compare(x: V, y: V): Boolean = ord.lteq(x,y)
  private def swap(i: Int, j: Int): Unit = {
    val aux = vector(i)
    vector(i) = vector(j)
    dict(vector(i)._1) = i
    vector(j) = aux
    dict(vector(j)._1) = j
  }
  private def replace(i: Int, j: Int): Unit = {
    dict -= vector(i)._1
    vector(i) = vector(j)
    dict(vector(i)._1) = i
    vector.remove(j)
  }

  private def insert(key: K, value: V): Unit = {
    vector += ((key, value))
    dict(key) = vector.size - 1
    bubbleUp(vector.size - 1)
  }

  private def delete(i: Int): Unit = {
    if (vector.size == 1) {
      dict -= vector(0)._1
      vector.remove(0)
    } else {
      replace(i, vector.size - 1)
      bubbleDown(i)
    }
  }

  def isEmpty(): Boolean = vector.isEmpty

  def enqueue(key: K, value: V): Unit = {
    if (!dict.contains(key)) {
      insert(key,value)
    }
    // TODO: handle when it already contains the key
  }

  @tailrec
  private def bubbleUp(i: Int): Unit = {
    val p = parent(i)
    if ((p != i) && (!compare(vector(p)._2, vector(i)._2))) {
      swap(p, i)
      bubbleUp(p)
    }
  }

  @tailrec
  private def bubbleDown(i: Int): Unit = {
    var largest = i
    val l = left(i)
    val r = right(i)
    if ((exists(l)) && (compare(vector(l)._2, vector(largest)._2))) {
      largest = l
    }
    if ((exists(r)) && (compare(vector(r)._2, vector(largest)._2))) {
      largest = r
    }

    if (largest != i) {
      swap(i, largest)
      bubbleDown(largest)
    }
  }

  def dequeue(): Option[(K, V)] = {
    val optionRoot = vector.headOption
    if (optionRoot.isDefined) {
        delete(0)
    }
    optionRoot
  }

  def dequeueAll(): Seq[(K,V)] = {
    val resp = ArrayBuffer[(K,V)]()
    var x = dequeue
    while (x.isDefined) {
      resp += x.get
      x = dequeue
    }
    resp
  }

  def headOption(): Option[(K,V)] = vector.headOption
  def get(k: K): Option[V] = {
    dict.get(k) match {
      case Some(i) => Some(vector(i)._2)
      case None => None
    }
  }

  // change values and heapify
  // * PriorityQueue does not have this feature
  def putValue(key: K, value: V): Unit = {
    val optionOldValue = get(key)
    if (optionOldValue.isDefined) {
      val oldValue = optionOldValue.get
      val i = dict(key)
      vector(i) = (key, value)
      if (compare(value, oldValue)) {
        bubbleUp(i)
      } else {
        bubbleDown(i)
      }
    } else {
      // if key does not exist, insert it
      insert(key,value)
    }
  }

  // different from dequeue, removes an arbitrary element
  def remove(key: K): Unit = {
    if (dict.contains(key)) {
      delete(dict(key))
    }
    // TODO: handle when it does not contain the key
  }
}