How to reprioritize something in a priority queue

I’m using scala.collection.mutable.PriorityQueue and I don’t see the method for changing the priority of an entry in the queue. Normally, there should be a method named something like decreasePriority, or increasePriority or changePriority, but I don’t see it. Can someone help?

I need such a function to implement the Dijkstra shortest path algorithm.

The priority is provided by the (implicit) Ordering of the element type. The queue cannot possibly know how to replace or change an element in order to tweak its priority.

You’ll need to remove the element and then enqueue a new element with the same “payload”, but the parts of the element that affect the ordering updated accordingly for the immutable case (recommended), or update the ordering-relevant parts of the original element and re-enqueue it for the mutable case.

1 Like

That’s bizarre that this class is missing the changeProprity method.

BTW, it is also not clear to me out to remove an arbitrary element from the scala.collection.mutable.PriorityQueue. I could remove it before I update the dist map.

Even if the ordering is provided by the (implicit) Ordering that does not mean the ordering won’t change, Dijkstra as a prime example. In my case I’m using Ordering.by(reverseDistance) , and the value that reverseDistance returns depends on the current value of the dist map which is updated on each step of the Dijkstra algorithm. I.e., every time a “shorter path” is found then the map is updated, and thereafter reverseDistance will return a different value than previously. However, something needs to notify the propriety queue that its assumption about the value is now invalid. Normally, this is done with a call to changeProprity.

    var dist = Map {
      source -> 0
    }

    def reverseDistance(v: A): Int = -dist(v)

    val q = new PriorityQueue[A]()(Ordering.by(reverseDistance))

In Common Lisp clheap, add-to-heap returns an index which can later be used as an argument to decrease-key.

Accepting as a given that the priority is provided by an Ordering, what should the signature of #changePriority() look like?

Yes, I see that the implicit Ordering is indeed problematic. It should have been implemented with a value-extractor function. I.e., the heap should be prioritized not by passing the object to the ordering compare function, but rather by passing the values returned by the value-extractor function to the compare function. By default the value-extractor whould of course be identity.

Perhaps it just needs a way for you to notify it that one of its entries has now become out of order, and needs to be shuffled back to the correct place?

BTW, is there a way to remove a target element from the queue which is NOT necessarily the minimum? If so, I could store pairs of (object, priority) rather than just objects. Then when the priority needs to change, I could remove the old pair and insert a new pair.

This thread relates to another thread: Priority queue and fibonacci queue/heap.
In that thread, someone suggested taking a look at: Functional Brodal Queues. But unfortunately, it appears to me that that implementation also omits reduce-min and delete-node.

Not necessarily – it’s a question of intended use cases. The class as defined looks like it works fine for a lot of them: basically the common situation where you want to be able to just insert elements and pull them out in order. That’s a valid interpretation of “priority queue” – it just isn’t as broad as you need for your use case, which looks like it needs a pretty different design.

(Although I suspect a tweaked version, that allows you to recompute the placement of a specific element, would suit your needs. You might want to consider trying to just copy and enhance the class.
I think the existing class is the way it is because it is assuming immutable elements, and your desired behavior only makes sense with mutable ones, I think.)

A heavyweight alternative to hypothetical
priorityQueue.remove(elem)
is
priorityQueue = priorityQueue.partition(_ == elem)._2
It rebuilds the whole priority queue.

Changing Ordering on the fly probably won’t work at all, as Ordering needs to consistent with items order at all time. Mutable Ordering breaks priority queues and ordered sets and maps. Mutable keys break priority queues and most sets and maps (hash-oriented, Ordering-oriented, etc). Only the inefficient sets, maps and priority queues survive items mutation, i.e. the ones that scan entire collection on every lookup.

Prioriy queues are based on heaps and heaps generally don’t provide efficient search method. To be able to efficiently manipulate a heap node (e.g. change its position or links to other nodes) you need direct handle to that node. Priority queues used in academic/ competitive programming expose that, but Scala’s standard PriorityQueue does not.

heavyweight, yes. As I understand the complexity of the Dijkstra is O(E + V logV). (E=number of edges, V=number of vertices). The logV comes from the fact that the reduce-min and extract-min are both O(log V). If reduce-min is implemented as you suggest, then it becomes O(V) at best and O(V log V) at worst. If partition builds the heap by greedily adding one element at a time, then its complexity is O(V log V). That will make the complexity of Dijkstra O(E + V^2 log V) which admittedly is still better than Bellman-Ford which is O(VE) = O(V^3)

The solution I’m using now is a bit different. Rather than building a queue of objects of type T, and a compare-function (T,T)=>Boolean, I am now building a queue of objects of type (T,Int) and the compare-function is (_._2 < _._2). I.e., ignore the object and just compare the integers. With the integer I set the propriety of each element explicitly when I add it to the queue.

If I want to change the priority of an object, I just add the object to the queue again (redundantly) with a new priority. However, I must keep an external mapping of object -> priority. Now, whenever I take an object from the queue (extract-min), I check to see whether it has the expected priority; if not, I ignore it and call extract-min again.

It’s a lot of work, and I am assuming that adding an object to a Map has Log(n) complexity. not sure whether that is too naïve of me.

Default Map is HashMap and it has amortized O(1) access time. Default SortedMap is TreeMap which has O(lg n) access time. https://docs.scala-lang.org/overviews/collections/performance-characteristics.html

If a single object is added to priority queue many times then probably that priority queue could be many times bigger than it should be. Therefore you could keep track of excessive items count and when that count is higher than valid items count you could do filtering, like:

val validPrioritiesMap: Map[T, Int] = ...
val filteredPriorityQueue = priorityQueue.filter { case (item, priority) => validPrioritiesMap.get(item).forall(_ == priority) }
1 Like