Scala与Java的TreeSet - TreeSet？

Question

如果我想删除Java的TreeSet中log(n)时间的最高值，我会使用treeSet.pollFirst() --什么等同于Scala的mutable.TreeSet类？

无论如何，我真正想要的是一个类似堆的优先级队列数据结构，它可以让我在对数时间内执行removeMax、add和updatePriority操作。我看了Scala集合库，我很困惑-虽然mutable.PriorityQueue让我在对数时间内deque (即removeMax) -但它没有提供在日志时间内更新优先级的方法(我将不得不在线性时间内粗略地扫描和删除项目并重新添加)。类似地，mutable.TreeSet可以让我在对数时间内更新优先级(通过粗略地删除和重新添加)，但它没有removeMax (即pollFirst)操作。我应该使用什么集合容器？请不要将我引用到外部依赖项。

Answer 1

您可以在immutable.TreeSet中使用head和last方法，它们是O(log n)。同样的方法也存在于mutable.TreeSet中，但是还没有被覆盖以提供更好的效率和摊余时间(在Scala2.10中)。head方法将是对数的，但在这样做时可能会实例化迭代器。last方法实际上将遍历它，具有线性复杂性。好消息是，您可以使用自定义的Ordering控制最小或最大的值-并通过调用Ordering.reverse从现有的Ordering中轻松地获取它。

如果需要删除该元素，只需使用-=。您可以创建自己的隐式值类来利用树集上的pollFirst方法。

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

Answer 2

不是一个答案，只是一个建议:)记住，您可以从scala访问Java库(好吧，如果您编译到JVM :)，所以如果Java的TreeSet适合您，请使用它:)

您还可以阐明您的需求；updatePriority方法的参数是什么？你想要更新的是谁的优先级？