更新排序列表
更新排序列表
提问于 2017-04-02 19:25:21
我想我正在搜索的算法有一个通用的名字。
我有一个很大的球员名单，根据他们的得分排序。例如，100万或10亿玩家。每隔一秒就有一个球员在改变它的分数，我希望更新排序列表来保持排序，我希望知道一个新的球员位置。
我可以更新分数并重新排序球洞列表。(效率不高)或者我可以从oldpos, newpos重新排序，或者我可以移动玩家和移动其他玩家。(最佳)
这样的算法有名字吗？
常规数据库不能有效地处理这项任务，我必须用Java、C#、Go等开发服务，将排序列表保存在内存中并进行移位，这是正确的吗？
回答 1
Stack Overflow用户
发布于 2017-04-02 21:26:04
你可以持有一个AVL tree，在这样的数据结构上进行插入和删除操作需要O(logn)时间。每次你需要更新一个玩家:从树中移除，更改分数，插入到树中。
这正是您正在寻找的权衡，所有的操作都需要O(logn)，因为您需要所有的操作(查找和更新-删除\插入)，这是最适合您的。内存消耗为O(n) btw。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43167750
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号