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
It’s a lot of work, and I am assuming that adding an object to a
Log(n) complexity. not sure whether that is too naïve of me.