algorithm - 排行榜的高效数据结构

Question

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

• 为给定玩家添加分数
• 检索给定玩家的最佳分数
• 检索给定玩家的排名
• 检索得分高于和低于当前玩家等级的玩家
• 支持不同的时间范围：今天的分数，本周，今年等。
• 扩展到约 100,000 名玩家
• 内存占用尽可能小（即在廉价机器上运行）

谢谢您的帮助！

Answer 1

解决方案是使用两种数据结构。更新操作将 O(n) 视为不仅给定的玩家，而且所有玩家的排名都必须重新计算。

We will use two DS for this:
    a. Balanced Binary Search Tree
    b. Hash Map

Each node of a Binary Search Tree is [Uid, Score, Reverse-rank]
    Uid: is the user id of a player.
    Score: is the score of a player.
    Reverse-rank: This is a rank of a player but in reverse order. The player scoring lowest will
    have this value as 1. The player scoring highest will have this value as the size of a BST.

    The Binary Search Tree is implemented based on the score of a player.

The Hash Map structure is as follows:
    Key: Uid
    Value: BST Node.

updateRank(userId, score)
    if player is new (userid not in map)
        1. Insert the player in a BST.
        2. Insert the player in a Map.
        3. Calculate Rank: If a node is inserted to right, then its rank will be one less than its
        parent. If a node is inserted to left, then its rank will be one more than its parent.

    if player is old (userid exists in map)
        1. Fetch the node from Map.
        2. if new score and old score is same then do nothing.
        3. Delete the old node.
        4. Insert the new node.
        5. Calculate Rank: Perform in-order and mark all the nodes from 1 to n (length).
           This op is expensive among all. It takes O(n)
    O(n)

getRank(userId)
    Find a node from the map.
    return rank as (n + 1) - reverse rank
    O(1)

display()
    Perform inorder traversal and return all the players.
    O(n)

NOTE: 1. The tree has to be balanced BST.
      2. We cannot use heap because, the display() would be difficult to implement. We would have
      to remove every element from heap which would take O(nlogn).

Answer 2

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