排行榜的高效数据结构

Mar*_*tin 6 algorithm data-structures

我想实现一个排行榜,我意识到尽管这似乎是一个简单的任务,但这可能变得非常复杂.我可以简单地使用具有适当索引的数据库,但我想知道是否有一个有效的数据结构可以支持以下操作.

  • 为给定玩家添加分数
  • 检索给定玩家的最佳分数
  • 检索给定玩家的等级
  • 检索当前玩家等级高于和低于分数的玩家
  • 支持不同的时间范围:今天的分数,本周,今年等.
  • 可扩展至约100,000名玩家
  • 内存占用尽可能小(即在便宜的机器上运行)

谢谢您的帮助!

uba*_*uba 0

您可以使用二叉搜索树(平衡树,如 AVL 或红黑树)来存储基于总得分的玩家信息。在玩家结构中,您可以针对不同的时间范围使用不同的数组,并使用单独的变量来表示总得分和最佳得分。查找排名或低于或高于某个玩家的玩家需要按顺序遍历。