data-structures - 什么样的数据结构符合这个描述？

Question

我需要一个数据结构，它包含唯一值（如集合），但也对它们进行排序（如优先级队列）并允许随机访问二进制搜索（如数组）。哪种类型的数据结构可以满足这些需求？我可以不用排序（最后我总是可以自己排序）

Answer 1

这听起来像是一棵平衡二叉树，在其插入操作中具有唯一性限制，并实现了该OS-SELECT操作（参见：算法简介，第 3 版中的第 14 章）以在给定其在 O 中的排名（“索引”）的情况下检索元素(lg n)。

建议的数据结构和增强的操作将允许您：

• 保持唯一值，在 O(lg n) 中执行插入操作
• 使用 O(lg n) 搜索操作保持元素排序
• 访问给定其在 O(lg n) 中的排名的元素

Answer 2

TreeSet或TreeMap怎么样？

• 唯一值 - 两者都只存储唯一值
• 排序 - 使用元素的自然顺序或提供给它们的自定义比较器对条目进行排序
• 随机访问 - 两者都提供随机 (O(1)) 访问。