Scala's TreeSet vs Java's TreeSet - poll?

Question

If I want to remove the highest entry in log(n) time in Java's TreeSet, I use treeSet.pollFirst() - what is the equivalent for Scala's mutable.TreeSet class?

Anyway, what I really want is a heap-like priority queue data structure that lets me removeMax, add and updatePriority in logarithmic time. I looked at the Scala collections library and I am confused - while mutable.PriorityQueue lets me deque (i.e. removeMax) in logarithmic time - it provides no way to update priority in log time (I would have to hackily scan and remove item and re-add in linear time). Similarly mutable.TreeSet would let me update priority in logarithmic time (by hackily deleting and re-adding) but it does not have a removeMax (i.e. pollFirst) operation. What collections container should I use? Please do not refer me to external dependencies.

Answer 1

You can use the head and last methods in the immutable.TreeSet, which are O(log n). The same methods exist in mutable.TreeSet, but have not been overridden to provide better efficiency and amortized time (in Scala 2.10). The head method will be logarithmic, but may instantiate an iterator when doing so. The last method will actually traverse it, having linear complexity. The good news is that you can control what is smallest or largest with a custom Ordering - and easily obtain it from an existing Ordering by calling Ordering.reverse.

If you need to remove that element, simply use -=. You can create your own implicit value class to piggy back the method pollFirst on the tree set.

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal {
  def pollFirst(): T = {
    val elem = ts.head
    ts -= elem
    elem
  }
}

Answer 2

Not an answer, just a suggestion :) remember that you can access Java libraries from scala (well, if you compile to the JVM :) so if Java's TreeSet works for you, use it :)

You can also clarify your requirements; what would be the parameters to your updatePriority method ? whose priority you trying to update ?