Let's say I am designing a scoreboard where I need to access and update player scores as fast as possible. The score of some players change often so I need to find that player and reorder the list. At each time step I need a sorted list of players from highest to lowest score. What data structure would offer both the fastest time to keep the scores sorted as well as allow a quick update for a random player?

If I went with a linked list, I could keep it sorted but it would take O(n) to find the player that needs to be updated.

Example:

class Player{
  string name;
  int score;
}

players.ListScores();

Output:

Players: Andrew 10, Phil 7, Larry 3, Joe 1

players.UpdatePlayer("Joe", 8);
players.GetTop(3);

Output:

Top 3 players: Andrew 10, Joe 8, Phil 7, Larry 3

I have knowledge of data structures but I can't remember which one would be best for this application. Is there one where I can keep the values in sorted order as well as update a score in less than O(n) time?

Memory isn't as much a requirement as speed.

  • Depending on what language you are using, you should be able to use a Dictionary or Hashtable which would be O(1). Some languages like C# offer a SortedDictionary that can keep the data sorted as well (based on Key). You may not need to keep it sorted though, you know the new score and if it is higher than your "top 3", you simply insert it where appropriate and knock the other one off. – Ron Beyer Oct 12 at 16:30

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.