有效百分位查找的数据结构？

Question

假设您有大量的键/值对,其中值是一些任意实数.您有兴趣创建支持以下操作的数据结构:

• Insert,为集合添加新的键/值对,
• 删除,从集合中删除键/值对,
• 百分,它告诉哪个百分与给定键相关联的值是,和
• Tell- Percentile,接受百分位数并返回其值为至少给定百分位数的最低值的键.

例如,该数据结构可以用于在接收全国范围的测试分数流时有效地确定给定学生的百分位数,或者识别具有异常好的或差的服务质量的医院.

有没有办法让这些操作有效运行(比如,次线性时间？)

Answer 1

实现此数据结构的一种可能方式是使用订单统计树和哈希表的混合.

订单统计树是一种平衡二叉搜索树,除了正常的二叉搜索树操作外,还支持另外两个操作:

• Rank(key),返回树中元素的数量小于给定元素,和
• 选择(k),它返回树中第k个最小元素.

可以通过增加正常平衡二叉搜索树(例如,红/黑树或AVL树)以及在旋转期间保留的额外信息来构建顺序统计树.通过这种方式,可以使订单统计树上的所有正常BST操作在O(log n)时间内运行,额外操作也在O(log n)时间内运行.

现在,让我们假设您纯粹存储值分数,而不是键/百分位数.在这种情况下,如下实现百分位查找将非常简单.将所有值存储在订单统计树中.要确定给定值的百分位数分数,请使用订单统计树上的排名操作来查找该值显示的索引.这给出了一个数字,范围从0到n - 1(其中n是树中元素的数量),表示该分数在订单统计树中的位置.然后,您可以将该数字乘以99 /(n - 1),以获得根据需要在0到99范围内运行的值的百分位数分数.

要确定大于某个百分位数的最低值,可以使用select操作,如下所示.给定0到99之间的百分位数,多个百分位数99 /(n - 1)得到0和n - 1之间的实数,包括0和n - 1.取该数字的上限会产生0到n - 1(包括0和n - 1)范围内的自然数.使用订单统计树上的选择操作,然后可以用于查找处于或高于给定百分位数的范围中的第一个值.

但是,这些操作假设我们在数据结构中具有纯值,而不是键/值对.为了使此操作适用于键/值对,我们将按如下方式扩充数据结构:

1. 我们将在每个节点中存储键/值对,而不仅仅是存储值.订单统计树将纯粹按其值对键/值对进行排序,密钥作为卫星数据携带.
2. 我们将存储一个二级哈希表,将密钥映射到它们的关联值.

这两项更改使我们可以为数据结构实现所需的功能.为了使数据结构按密钥进行百分位查找,我们首先使用给定的密钥查询哈希表以查找其关联值.然后,我们对值进行百分位查找,如前所述.为了使数据结构告诉我们一个值为第一个等于或高于给定百分位数的密钥,我们在订单统计树上执行正常的查找百分位操作,如上所述,然后查找与给定值相关联的密钥.

如果我们假设哈希表使用链式散列,那么每个操作所需的时间如下:

• 插入:O(log n)时间将值/密钥对插入订单统计树,加上O(1)摊销时间以将密钥/值对插入哈希表.总时间为O(log n)摊销.
• 删除:O(log n)时间从订单统计树中删除值/密钥对,加上(1)从哈希表中删除密钥/值对的分摊时间.总时间为O(log n)摊销.
• 百分位:O(1)预期时间查找与密钥相关联的值,O(log n)时间进行排名操作,O(1)额外时间将排名映射到百分位数.总时间是预期的O(log n).
• Find- Percentile:将百分位数映射到排名所需的O(1)时间,以及执行选择操作所需的O(log n)时间.总时间是O(log n)最坏情况.

希望这可以帮助!