假设您有大量的键/值对，其中值是一些任意实数。您有兴趣创建支持以下操作的数据结构：
- 插，它为集合添加了一个新的键/值对，
- 删除，从集合中删除键/值对，
- 百分，它告诉与给定密钥相关的值在哪个百分位，和
- 推荐给百分，它接受百分位数并返回其值为至少给定百分位数的最低值的键。
例如，该数据结构可以用于在接收全国范围的测试分数流时有效地确定给定学生的百分位数，或者识别具有异常好或坏的服务质量的医院。
有没有办法让这些操作有效运行（比如，次线性时间？）
假设您有大量的键/值对，其中值是一些任意实数。您有兴趣创建支持以下操作的数据结构：
例如，该数据结构可以用于在接收全国范围的测试分数流时有效地确定给定学生的百分位数，或者识别具有异常好或坏的服务质量的医院。
有没有办法让这些操作有效运行（比如，次线性时间？）
实现此数据结构的一种可能方式是使用a的混合 订单统计树 和a 哈希表。
订单统计树是一种平衡二叉搜索树，除了正常的二叉搜索树操作外，还支持另外两个操作：
可以通过扩充正常的平衡二叉搜索树（例如，a。）来构建订单统计树 红/黑树 或者 AVL树）具有在旋转期间保留的额外信息。通过这种方式，可以使订单统计树上的所有正常BST操作在O（log n）时间内运行，额外操作也在O（log n）时间内运行。
现在，让我们假设您纯粹存储值分数，而不是键/百分位数。在这种情况下，如下实现百分位查找将非常简单。将所有值存储在订单统计树中。要确定给定值的百分位数分数，请使用 秩 在订单统计树上操作以查找该值出现的索引。这给出了一个数字，范围从0到n - 1（其中n是树中元素的数量），表示该分数在订单统计树中的位置。然后，您可以将该数字乘以99 /（n - 1），以获得根据需要在0到99范围内运行的值的百分位数分数。
要确定大于某个百分位数的最低值，您可以使用 选择 操作如下。给定0到99之间的百分位数，多个百分位数99 /（n - 1）得到0到n - 1之间的实数，包括0和n - 1。取该数字的上限会产生0到n - 1（包括0和n - 1）范围内的自然数。使用 选择然后，可以使用订单统计树上的操作来查找处于或高于给定百分位数的范围中的第一个值。
但是，这些操作假设我们在数据结构中具有纯值，而不是键/值对。为了使此操作适用于键/值对，我们将按如下方式扩充数据结构：
这两项更改使我们可以为数据结构实现所需的功能。为了使数据结构按键进行百分位查找，我们首先使用给定键查询哈希表以查找其关联值。然后，我们对值进行百分位查找，如前所述。为了使数据结构告诉我们一个值为第一个等于或高于给定百分位数的密钥，我们在订单统计树上执行正常的查找百分位操作，如上所述，然后查找与给定值相关联的密钥。
如果我们假设哈希表使用链式散列，那么每个操作所需的时间如下：
希望这可以帮助！
有一种简单而高效的可能性：
如果你只能在最终填满的学生结构中搜索百分位数，那么：
当您不知道元素的数量时，使用ArrayList动态构建。
如果你知道它们，那么直接从数组开始，否则从动态数组创建数组。 （例如java中的ArrayList）。
插：不是必要的，取而代之的是在最后添加，并排序一次。
删除：不是必要的，如果你可以忍受。
告诉百分：更简单：非常接近的东西：element [length * percentile]：O（1）
在实践中，阵列方法将比平衡树方法快得多，至少在java中， 当你的应用程序可以建立一次数组（例如每日学生评估，每天建立它）
我已经使用自编写的ArrayListInt实现了上面的（my）算法，它与ArrayList相同但使用原始类型（double，int），而不是对象类型。当所有数据都被读取时，我对它进行了一次排序。
进一步你想要的关键价值：
我只想添加一个树形图（平衡树）。现在，如果TreeMap和附加百分位数组有意义，那就有点怀疑了：那取决于你搜索的频率，以及内存使用与搜索时间的关系。
更新：
结果：treeset vs sorted array（动态构建数组，然后最后排序一次：
num elements: 1000 treeSet: 4.55989 array=0.564159
num elements: 10000 treeSet: 2.662496 array=1.157591
num elements: 100000 treeSet: 31.642027 array=12.224639
num elements: 1000000 treeSet: 1319.283703 array=140.293312
num elements: 10000000 treeSet: 21212.307545 array=3222.844045
现在这些元素（1e7）接近极限（1GB堆空间），在下一步中，内存将耗尽（已经在1e7处发生，但是在树集之后清理内存，测量1e7的运行也起作用）。
缺少的是搜索时间，但带有binsearch的排序数组只能通过哈希表来打败
最后： 如果你可以建立一次学生集，例如每天，那么使用数组方法可以提供更简单的百分位数搜索。