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

发布时间：2020-12-16 08:54:24 所属栏目：安全来源：网络整理

导读：如果我想在 Java的TreeSet中删除log(n)时间中的最高条目,我使用treeSet.pollFirst() – Scala的mutable.TreeSet类的等价物是什么？无论如何,我真正想要的是一个类似堆的优先级队列数据结构,它允许我以对数时间删除Max,add和updatePriority.我查看了Scala集

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

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

解决方法

您可以使用immutable.TreeSet中的head和last方法,它们是O(log n).
mutable.TreeSet中存在相同的方法,但是没有被覆盖以提供更好的效率和摊销时间(在Scala 2.10中). head方法将是对数的,但是在执行此操作时可以实例化迭代器.最后一种方法实际上会遍历它,具有线性复杂性.好消息是,您可以使用自定义排序控制最小或最大的内容 – 并通过调用Ordering.reverse轻松地从现有订单中获取.

如果您需要删除该元素,只需使用 – =.您可以创建自己的隐式值类,以便在树集上备份方法pollFirst.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!