Suggestion for a data structure for ranking users based on scores

Question

I'm looking to use create and maintain the ranks in memory.

Scores associated with user ids and ranks are computed based on the scores. The following functionality should be supported.

• Sort ranks based on scores ascending or descending. Insertion or deletion in O (log n) time.
• Given a user id, lookup user’s rank/score along with n preceding and succeeding ranks in O(log n) time. E.g. get ranks of user 8347 with 5 preceding and succeeding ranks.
• Retrieve n number of ranks from any offset x. E.g. get 100 ranks starting from 800

Given these requirements, are there any suggestions on which data structure suits these requirements the best?

Answer 1

I think you can do this very efficiently using a combination of an order statistic tree and a hash table.

An order statistic tree is an augmented binary search tree that in addition to storing elements in sorted order, allows for lookup of elements by their index in the tree. That is, the structure supports O(lg n) insertion, deletion, and lookup of values by their key, as well as O(lg n) lookup of an element given its index. If you store the scores in this structure, you can easily insert or update new scores, as well as keeping track of the rank of each element in the tree.

In order to associate users with their scores, you could combine this structute with an auxiliary hash table mapping from user IDs to the nodes in the order statistic tree holding the score for that user. This would give you O(1) access to a player's score in addition to the O(lg n) lookup of a score's rank.

Hope this helps!