有效排序的数据结构，支持重复键 [英] Efficiently ordered data-structure that supports duplicate keys

问题描述

我正在寻找一种数据结构，该结构可以有效地在插入时对对象进行排序.我想根据特定变量的值(在这种情况下为适应性)对这些对象(在这种情况下为个人)进行排序.

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

如果我将个人插入有序列表中，效率将降至O(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 ArrayList and 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.

这篇关于有效排序的数据结构，支持重复键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！