8

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

无论如何，我真正想要的是一个类似于堆的优先队列数据结构，它可以让我在removeMax对数时间内。我查看了 Scala 集合库，我很困惑 - 虽然让我（即）在对数时间内 - 它没有提供更新日志时间优先级的方法（我将不得不粗暴地扫描和删除项目并在线性时间内重新添加） . 同样可以让我在对数时间内更新优先级（通过删除和重新添加），但它没有（即）操作。我应该使用什么收藏容器？请不要向我介绍外部依赖项。addupdatePrioritymutable.PriorityQueuedequeremoveMaxmutable.TreeSetremoveMaxpollFirst

4

2 回答 2

3

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

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

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal {
  def pollFirst(): T = {
    val elem = ts.head
    ts -= elem
    elem
  }
}
于 2013-04-04T12:26:02.227 回答
1

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

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

于 2013-04-04T12:55:16.867 回答