什么数据结构符合这个描述？

我需要一个保存唯一值的数据结构（比如一个集合），还要对它们进行排序（如优先级队列），并允许随机访问二进制搜索（如数组）。哪种类型的数据结构可以满足这些需求？我可以生活在没有排序（我总能在最后自己对其进行排序）什么数据结构符合这个描述？

来源

2012-06-17 baruch

这听起来像一个平衡二叉树，有独特性在其插入操作的限制，贯彻OS-SELECT操作（参见：Introduction to Algorithms，章（第3版中的14），用于检索给定其在O（lg n）中的等级（“索引”）的元素。

所提出的数据结构和增强业务将允许您：

保持独特的价值观，为O执行插入操作（LG N）
保持的元素进行排序，用O（LGñ ）搜索操作
访问O（LGñ鉴于其排名的元素）

来源

2012-06-17 19:10:48

随机存取就像一个数组？ –

@KingsIndian：OP没有为随机访问指定期望的时间复杂度... –

@OliCharlesworth由于OP提到了“like-an-array”，我认为OP期望恒定时间访问。 –

怎么样TreeSet或TreeMap？

唯一值 - 两个商店的唯一值仅
排序 - 两个排序的条目或者使用元件或由它们提供
随机接入的定制比较自然顺序 - 两者都提供随机（O（1））访问。

来源

2012-06-18 00:35:26 nhylated

这个问题没有指定数据结构必须在Java中实现。此外，'TreeSet'和'TreeMap'都是平衡二叉树，实现为红黑树。你的最后一点是不正确的，他们不提供O（1）随机访问。对于'TreeMap'，文档为'containsKey'，'get'，'put'和'remove'操作指定O（lg n）时间成本，为add，'remove'和'contains'操作指定O（lg n） 'TreeSet' –

什么数据结构符合这个描述？

回答

相关问题