Proposing a data structure for ranking users based on ratings

Question

I want to use creating and storing ranks in memory.

The ratings associated with user identifiers and rankings are calculated based on the ratings. The following features must be supported.

• Sorting ranks based on ratings ascending or descending. Insert or delete in O (log n) time.
• Given the user ID, search users rate / rate along with n previous and subsequent ranks in O (log n) time. For instance. Get user rows 8347 with 5 previous and next rows.
• Get n number of ranks from any offset x. For instance. get 100 ranks starting at 800

Given these requirements, are there any suggestions for which a data structure is best suited for these requirements?

Answer 1

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

The order statistics tree is an extended binary search tree that, in addition to storing items in a sorted order, allows you to search for items by their index in the tree. That is, the structure supports O (lg n) insertion, deletion and search of values ​​by their key, as well as O (lg n) search for an element taking into account its index. If you store ratings in this structure, you can easily insert or update new ratings, as well as track the rank of each item in the tree.

To associate users with their ratings, you can combine this structure with an auxiliary mapping of the hash table from user identifiers into nodes in the order statistics tree containing the rating for this user. This will give you O (1) access to the player’s account in addition to finding a zero rating of O (lg n).

Hope this helps!

Answer 2

Use in-memory SQLite database.

Answer 3

What about the priority queue?

Each person will have an assessment, transfer it to the priority queue, and he will perform the work of sorting in ascending / descending priority / value / rank / etc.

Answer 4

binary search tree, one implementation - http://en.wikipedia.org/wiki/AA_tree

Space O(n) O(n) Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(log n) O(log n)