Mohan - 1 year ago 90

Scala Question

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`

`update`

*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?

Answer Source

`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