实现高scrores表的最佳数据结构是什么
提问于 2013-12-20 04:44:30
我正在尝试实现一个游戏的高分数表。我认为最好的解决方案是创建一个链表，然后在表中插入新的分数，然后遍历列表直到该点，并将所有排名下移一个。有没有更好的替代方案？
回答 2
Stack Overflow用户
发布于 2013-12-20 04:49:33
Stack Overflow用户
发布于 2013-12-21 10:32:01
我想说的是，一个平衡的二进制搜索树(Red-Black/AVL)与手指(指向树中的最大值)将是非常有效的。您可以在O(1)中获得最高分，并且通过获取前置节点(这在BVS中很简单)，您可以获得任意多的高分。
如果你有一堆分数，并且希望能够挑选出x排名前几的分数，这将是非常有用的。如果你想要有一个获得分数并返回其排名的函数，或者想要询问一般的范围查询(即“给我从10到20的排名”)，你需要稍微修改一下结构(保持每个节点中子树的大小并使用该信息)。
您的解决方案相当慢，每次插入和查找都需要O(n)次操作。堆在寻找最高分数方面要快得多，但是，它只给出最高分数-你必须手动搜索最高的x分数；而且，一般的范围查询不可能有效地完成。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20696447
复制相关文章
点击加载更多
腾讯云开发者
