Priority Queue - update priority?

[Tim Vergenz]

I'm using a priority queue and am trying to figure out the best way to go about updating priorities. At the moment it looks like the only way to do that in Scala is by rebuilding the collection.

I'm interested in improving that with some way of explicitly updating the priority of an individual element, but I wanted to see what people's thoughts are first. Some things that come to mind for me:

- Since priorities are implicitly encoded in the Ordering that gets passed in, the operation would have to be called something along the lines of "update" or "refresh" to indicate that it's just re-evaluating the Ordering for that element.
- Perhaps an alternative solution would be to implement a "remove" operation (with update then accomplished by removing and re-adding)? This may make it clearer what is going on as "updatePriority" or "updateOrdering" may not adequately convey what's happening (and I don't know what name would), though it would cost slightly more than an update (both in terms of runtime, but also it would require more new code; see next point).
- Most of the plumbing for an update command already exists internally; it would just have to be sanely exposed.

Some questions:

- Would there be any compatibility concerns with this? Would it go in 2.12 or 2.13?
- Do you think such an implementation is worthwhile?

To the second question, I think this is definitely a reasonably-sized and reasonably necessary addition. There isn't really a good option for accomplishing this with the standard implementation right now, and the only reasonable-cost way around that is a custom implementation of a priority queue.

What do you think?

[Rex Kerr]

Because priority queues use a heap internally, you can only find an internal element in O(n).  This makes remove an expensive operation.  It might make sense to implement it anyway, but what about the workaround of having a way to mark an element as defunct and just leaving it there, re-inserting a new non-defunct copy later?  This gets us back into O(log n)-like cost per element instead of O(n).

  --Rex

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.