java - java中哪种数据结构可以在恒定时间添加键/值对并保持按值排序？

Question

基本上我正在寻找 java 中的最佳数据结构，我可以存储对并按值检索前 N 个元素。我想在 O(n) 时间内完成此操作，其中 n 是数据结构中的整体数。

示例输入是，

<"john", 32>
<"dave", 3>
<"brian", 15>
<"jenna", 23>
<"rachael", 41>

如果 N=3，如果我想要降序，我应该能够返回 rachael、john、jenna。

如果我使用某种 hashMap，插入速度很快，但按顺序检索它们会很昂贵。如果我使用一些保持有序的数据结构，那么插入变得昂贵而检索更便宜。我没能找到既能做得又好又快的最佳数据结构。

欢迎任何意见。谢谢。

[更新]

让我以其他方式问这个问题，如果这样更清楚的话。我知道我可以在恒定时间 O(1) 中插入 hashMap。现在，我如何在 O(n) 时间内按值从排序顺序中检索元素，其中 n = 数据结构中的整体数量？希望它有意义。

Answer 1

如果要排序，就得放弃常数O(1)的时间。

这是因为与插入未排序的键/值对不同，排序将最低限度地要求您将新条目与某些东西进行比较，而概率是与许多东西进行比较。一旦您的算法需要更多时间处理更多条目(由于更多比较)，您就超出了“恒定”时间。

如果你能做得更好，那么一定要这样做!即使没有菲尔兹奖，也有 Dijkstra 奖等着你。

不要灰心，您仍然可以将关键部分作为一个 HashMap 来完成，而排序部分则使用类似树的实现，这将为您提供 O(log n)。 TreeMap 可能是您想要的。

--- 更新以匹配您的更新---

不，您不能在 O(n) 时间内迭代 HashMap 。这样做会假设您有一个列表；但是，该列表必须已经排序。使用原始 HashMap，您必须在整个映射中搜索下一个“较低”值。搜索 map 的一部分是行不通的，因为您没有检查的一个元素可能是正确的值。

现在，有一些数据结构可以做出很多权衡，这可能会让你更接近。如果您想自己滚动，也许自定义 Fibonacci 堆可以为您提供接近您希望的摊销性能，但它不能保证最坏情况下的性能。在任何情况下，某些操作(如 extract-min)仍然需要 O(log n) 性能。