Best tree/heap data structure for fixed set of nodes with changing values + need top 20 values?
- by user350139
I'm writing something like a game in C++ where I have a database table containing the current score for each user. I want to read that table into memory at the start of the game, quickly change each user's score while the game is being played in response to what each user does, and then when the game ends write the current scores back to the database. I also want to be able to find the 20 or so users with the highest scores. No users will be added or deleted during the short period when the game is being played. I haven't tried it yet, but updating the database might take too much time during the period when the game is being played.
Fixed set of users (might be 10,000 to 50,000 users)
Will map user IDs to their score and other user-specific information.
User IDs will be auto_increment values.
If the structure has a high memory overhead that's probably not an issue.
If the program crashes during gameplay it can just be re-started.
Quickly get a user's current score.
Quickly add to a user's current score (and return their current score)
Quickly get 20 users with highest score.
No deletes.
No inserts except when the structure is first created, and how long that takes isn't critical.
Getting the top 20 users will only happen every five or ten seconds, but getting/adding will happen much more frequently.
If not for the last, I could just create a memory block equal to sizeof(user) * max(user id) and put each user at user id * sizeof(user) for fast access. Should I do that plus some other structure for the Top 20 feature, or is there one structure that will handle all of this together?
