Scala的TreeSet与Java的TreeSet - 民意调查？

Question

如果我想删除log(n)Java中的最高条目TreeSet,我会使用treeSet.pollFirst()- Scala mutable.TreeSet类的等价物是什么？

总之,我真正想要的是一个堆状的优先级队列中的数据结构,让我removeMax,add并updatePriority在对数时间.我看了Scala集合库,我很困惑 - 虽然mutable.PriorityQueue让我deque(即removeMax)在对数时间 - 它没有提供更新日志时间的优先级(我必须hackily扫描和删除项目并重新添加线性时间) .同样mutable.TreeSet会让我在对数时间内更新优先级(通过hackily删除和重新添加),但它没有removeMax(即pollFirst)操作.我应该使用什么样的集合容器？请不要将我介绍给外部依赖项.

Answer 1

您可以使用中的head和方法，它们是。中存在相同的方法，但尚未被重写以提供更好的效率和摊销时间（在 Scala 2.10 中）。该方法将是对数的，但这样做时可能会实例化一个迭代器。该方法实际上会遍历它，具有线性复杂度。好消息是，您可以通过自定义控制最小或最大的值- 并通过调用轻松从现有的获取它lastimmutable.TreeSetO(log n)mutable.TreeSetheadlastOrderingOrderingOrdering.reverse。

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

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