支持重复键的高效有序数据结构
我正在寻找一种可以在插入时有效地对对象进行排序的数据结构。我想根据特定变量的值（在本例中为适应度）对这些对象（在本例中为个体）进行排序。
数据结构应该允许重复的键，因为特定的适应度值可能出现在不同的个体中。这是一个问题，因为例如 TreeMap 数据结构不允许重复的键。我更喜欢使用这种类型的树状结构，因为它的效率为 O(log N)。
如果我将个体插入有序列表中，效率将下降到 O(n)，并且在插入个体后对其进行排序也不会很有效。
是否存在一种高效的数据结构，使个体保持有序并支持重复键？
在创建数据结构后，我将经常添加和删除条目，因此在创建结构后对对象进行排序将非常昂贵。
I am looking for a data structure that orders objects at insertion efficiently. I would like to order these objects (in this case individuals) based on the value of a particular variable (in this case the fitness).
The data structure should allow duplicate keys since a particular fitness value can occur in different individuals. This is a problem because for example the TreeMap data structure does not allow duplicate keys. I would prefer to use this type of tree-like structure because of it's efficiency O(log N).
If I inserted the individuals in an ordered list, the efficiency would drop to O(n), and sorting the individuals after they have been inserted wouldn't be very efficient either.
Is there a data structure that is efficient, keeps the individuals ordered and supports duplicate-keys?
I will be adding and removing entries very often after the data structure has been created so sorting the objects after the structure has been created would be very expensive.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
Apache Commons 和 < a href="https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/Multimap.html" rel="nofollow">Guava 支持多重地图，这就是您正在寻找的。
或者，根据您的用例，您可以将元素收集在
ArrayList中，然后在 O(n lg n) 总时间内对其进行排序。或者，您可以定义一个比较，首先检查适合度，如果适合度比较相等，则检查项目的其他区别属性。
Both Apache Commons and Guava support multimaps, which are what you're looking for.
Alternatively, depending on your usecase, you could gather the elements in an
ArrayListand sort it afterwards in O(n lg n) total time.Or, you could define a comparison that checks fitness first and other distinguishing properties of the items if the fitnesses compare equal.
在经典计算机科学中，您正在寻找的数据结构称为优先级队列。
恰好从java 1.5开始，标准java类库就有了一个实现： java.util.PriorityQueue。
我会用它。
In classical computer science, the data structure you are looking for is called a Priority Queue.
It just so happens that since java 1.5, the standard java class library has an implementation: java.util.PriorityQueue.
I would use it.
如果您想使用常规的 TreeMap，您可以让它存储值包装器而不是值本身。然后，这些包装器将使用相同的密钥存储多个。
否则，您可以使用某种基于二叉搜索树的排序列表结构。我不久前写了一篇文章，可以在这里找到： http://www.scottlogic.co .uk/2010/12/sorted_lists_in_java/ 但我确信存在更多标准实现。这种结构的优点是contains(Object)方法以对数时间而不是线性时间运行。
If you want to use a regular
TreeMapyou could make it store value wrappers instead of the values themselves. These wrappers would then store multiple with the same key.Otherwise you could use some kind of sorted list structure, based on a binary search tree. I wrote one a while ago which is available here: http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/ but I'm sure more standard implementations exist. The advantage of this kind of structure is that the
contains(Object)method runs in time logarithmic rather than linear time.如果您只关心添加所有个体后的顺序，并且之后不添加任何新个体，那么对 ArrayList 进行排序可能是最快的选择。
否则，您可以使用 TreeSet，并有一个比较器，首先按适应度进行比较，然后再按 身份哈希代码（如果适合度相等（或通过任何其他不同属性））。因此，您的所有对象都会有所不同，但它们将按适合度排序。
If you only care about the order once all the individuals have been added, and don't add any new individual afterwards, then sorting an ArrayList is probably the fastest option.
Else, you may use a TreeSet, and have a comparator that compares by fitness first, and then by identity hash code if the fitnesses are equal (or by any other distinct property). All your objects will thus be different, but they will be sorted by fitness.