1

Priority queues support a 'decrease key' operation (https://en.wikipedia.org/wiki/Priority_queue#Summary_of_running_times), it is needed for a number of best first search type algorithms. It should run in O(log n) time. Does scala.collection.mutable.PriorityQueue support this efficiently?

Looking through the API docs the closest thing I can find is

def update (idx: Int, elem: A) : Unit
Replaces element at given index with a new value.

But there are two potential problems with this… firstly one has to find the element and it's not clear what the time complexity of findIndexOf is.* Second it looks like update allows the value to be increased as well as decreased; it's not clear whether that can be implemented efficiently.

*See e.g. How to implement O(logn) decrease-key operation for min-heap based Priority Queue? for proof that this can be done efficiently.

Does anyone know what the time complexity of update is?

Community
  • 1
  • 1
Mohan
  • 7,302
  • 5
  • 32
  • 55

1 Answers1

3

scala.collection.mutable.PriorityQueue does not support a decrease-key operation.

To implement a PQ with decrease-key operation, one must augment a typical PQ implementation with an additional data structure for indexing.

The accepted answer to the post you reference, How to implement O(logn) decrease-key operation for min-heap based Priority Queue, illustrates how to do this.

The Java standard library also does not contain an indexed priority queue.

You can find one Java implemenation on the Princeton Algorithms site.

There is a Scala version of the above located here

Community
  • 1
  • 1
TRuhland
  • 126
  • 1
  • 5