请大牛支招排名算法

VIP_fuck

大概意思是这样：有很多用户，用户有各种信息，还有个人积分。

希望能多这些人的积分做一个排名，除了能快速排名之外，还要快速获取指定用户的排名。

大牛指教。

windoze

http://www.boost.org/doc/libs/1_ ... ndex/doc/index.html

VIP_fuck

回复 2# windoze

多谢多谢，以前接触过这个，不过当时没细看，现在要不是大猫提醒，也没想起来。
只是临时用 multiset 做个比较傻的处理。

研究研究，多谢多谢。

lxyscls

VIP_fuck 发表于 2017-04-12 12:00
大概意思是这样：有很多用户，用户有各种信息，还有个人积分。

希望能多这些人的积分做一个排名，除了能 ...

《算法导论》

第14章数据结构的扩张
14.1动态顺序统计

扩张红黑树，在保证全部顺序的情况下，也能定位到某个元素的顺序（rank）

你也可以用redis存，它提供了sorted set，其内部实现是skip-list（《Redis设计与实现》这么讲的）

https://redis.io/commands#sorted_set

VIP_fuck

回复 4# lxyscls

多谢指教，我先试试大猫提供的办法。
然后学习一下这个红黑树扩展。

时间有限，只能先有功能再优化。

cokeboL

游戏业内比较普遍的做法是4楼说的 redis skiplist

windoze

其实每次插入删除的时候把每个用户的排名调一下就行了。
如果插入删除不多的话这么最省事。

cokeboL

还有人用堆排序的，up down fix，也ok

action08

堆排序固然独特，但是场景有限，游戏排名不对口

lxyscls

回复 8# cokeboL

minheap只能保证第一个最小呀，heap[2i+1]和heap[2(i+1)]只能保证比heap大，请问排序怎么玩呢？