java - 支持重复键的高效有序数据结构

Question

我正在寻找一种数据结构，它可以在插入时有效地对对象进行排序。我想根据特定变量的值(在本例中为适应度)对这些对象(在本例中为个体)进行排序。

数据结构应允许重复键，因为特定的适应度值可能出现在不同的个体中。这是一个问题，因为例如 TreeMap 数据结构不允许重复键。我更愿意使用这种树状结构，因为它的效率为 O(log N)。

如果我将个体插入有序列表中，效率将下降到 O(n)，并且在插入个体后对其进行排序也不会非常有效。

是否有一种高效的数据结构，使个体保持有序并支持重复键？

我会在创建数据结构后经常添加和删除条目，因此在创建结构后对对象进行排序会非常昂贵。

Answer 1

两者都是Apache Commons和 Guava支持多图，这正是您正在寻找的。

或者，根据您的用例，您可以在 ArrayList 中收集元素然后在 O(n lg n) 总时间内对其进行排序。

或者，您可以定义一个比较，首先检查适应度，如果适应度比较相等，则检查项目的其他区别属性。