java - Scala 的 TreeSet 与 Java 的 TreeSet - 轮询？

Question

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

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

Answer 1

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

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

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