建议基于分数对用户进行排名的数据结构

Question

我正在寻求使用创建和维护内存中的排名.

与用户ID和排名相关联的分数基于分数计算.应支持以下功能.

• 根据分数上升或下降对排名进行排序.在O(log n)时间内插入或删除.
• 给定用户ID,在O(log n)时间内查找用户的排名/分数以及n个前后排名.例如,获得具有5个前后排名的用户8347的排名.
• 从任何偏移x中检索n个排名.例如,从800开始获得100个排名

鉴于这些要求,对于哪种数据结构最适合这些要求有什么建议吗？

Answer 1

我认为您可以使用订单统计树和哈希表的组合非常有效地完成此操作.

订单统计树是增强二进制搜索树,除了以排序顺序存储元素之外,还允许通过树中的索引查找元素.也就是说,该结构通过其键支持O(lg n)插入,删除和查找值,以及给定其索引的元素的O(lg n)查找.如果将分数存储在此结构中,则可以轻松插入或更新新分数,以及跟踪树中每个元素的等级.

为了将用户与他们的分数相关联,您可以将此结构与从用户ID映射到订单统计树中的节点的辅助哈希表结合,并保存该用户的分数.除了O(lg n)查找分数排名之外,这还可以让你(1)访问玩家的分数.

希望这可以帮助!