排序算法请教

zliming

struct UserInfo
{
    string username;
    int    index;
};
#include <set>
struct UserNameLess
{
    bool operator()(UserInfo* u1, UserInfo* u2)
    {
        return u1->username < u2->username;
    }
};
set<UserInfo*, UserNameLess> nameList;
vector<UserInfo*> rank;

UserInfo puser = new UserInfo;
nameList["xxx"] = puser;
rank.push_back(puser);

zliming

vector排名原来有序的，当排名改变，从新排名位置到原排名位置重新排序，交换的是指针，不会慢的

glasslion

原帖由 emacsnw 于 2009-4-16 21:12 发表
Fibonacci heap的一个典型应用。。。

太恐怖了，那个东东不是只有理论意义吗

egmkang

原帖由 action08 于 2009-4-21 23:29 发表




红黑树是不是性能差于二叉树的？

PS，数据结构的很多概念都的不记得了

二叉树不一定是平衡的，红黑是平衡树，据说效率比AVL好。
以前看什么书上面说Linux内核进程调度用红黑树。

daybreakcx

红黑树是一种特殊的二叉查找树，其添加、删除和查找的时间复杂度都是O(logn)，n是几点的个数，STL里面的有些结构就是基于红黑树来实现的。红黑树的平衡性不如AVL好，AVL要求左右子树高度差不超过1，而红黑树没有这个限制，但是他就是利用染色使得时间仍然处于对数级别，而且统计效果据说是好于AVL的