CODEWITHSUNDEEP
data-structures
bob
bob

Reputation: 135

What is the best data structure for implementing a high scrores table

I am trying to implement a high score table for a game. I think that the best solution would be to create a linked list, and then just insert the new score on the table, and then run through the list up to that point and move all the rankings down one. Is there a better alternative to this?

Upvotes: 0

Views: 327

Answers (2)

TJ27
TJ27

Reputation: 308

I'd say that a balanced binary search tree (Red-Black/AVL) with finger (pointing to the maximum in the tree) would be quite efficient. You can get to the highest score in O(1) and via getting predecessor nodes (which is simple in a BVS), you can get as many high scores as you wish.

This would be useful if you have a bunch of scores and want to be able to pick x top ones. If you wanted to have a function which gets score and returns its ranking, or wanted to ask general range queries (i.e., "give me ranks from 10 to 20), you would need to modify the structure slightly (keeping the size of subtrees in each node and using that information).

Your solution is quite slow, requiring O(n) operations per insert and find. Heap is a lot faster in finding top score, however, it gives you only the highest score - you would have to manually search for top x scores; also, general range queries would be impossible to be done efficiently.

Upvotes: 0

Elliott Frisch
Elliott Frisch

Reputation: 201467

I think the best solution is to use a Priority Queue (which is usually implemented with a heap), that way new scores can simply be added and the data structure will sort it for you.

A priority queue built with a heap

Upvotes: 2

Related Questions