CODEWITHSUNDEEP
c++calgorithmdata-structuresdisjoint-sets
sudeepdino008
sudeepdino008

Reputation: 3364

Heuristics by weight and path compression

Generally heuristics by rank and path compression are used to achieve fast disjoint-set data structure operations. Somehow, I find heuristics by weight and path compression more sensible to me. Does the following implementation achieve the same running time as a heuristics by rank and path compression?

NOTE: rank used in the structure node is a misnomer, it refers to the number of children rather than the height of tree( which rank generally mean)

//using heuristics by weight and path compression to improve running time
typedef struct n{
    struct n *parent;
    int u,v,weight;
    int rank;        //if node is the parent, it keeps track of number of children. if not, it is -1.
}node;

node* MAKE(int u, int v, int weight)
{
    node *n=(node*)malloc(sizeof(node));
    n->parent=n;
    n->u=u;
    n->v=v;
    n->weight=weight;
    n->rank=0;
    return n;
}

node *FIND(node *n)
{
    if(n->parent==n)
        return n;
    n->parent=FIND(n->parent);
    return n->parent;
}

void MERGE(node *n1, node *n2)     //merge n1 and n2 and store in n1.
{
    assert(n1->rank!=-1);
    assert(n2->rank!=-1);
    if(n1->rank<n2->rank)
    {
        MERGE(n2,n1);
        return ;
    }
    n2->parent=n1;
    n1->rank=n1->rank+n2->rank+1;
    n2->rank=-1;
}

Upvotes: 0

Views: 716

Answers (1)

saeedn
saeedn

Reputation: 3378

You used both weight and rank in your structure! If by weight you mean weighted-merge heuristic, that is what usually rank is for (and by rank, I mean the height of tree as you noted, not number of children).

Keeping track of number of children does not give you any optimization! Because the complexity of Find is a function of height of tree not number of children in the tree that our input node is in too.

Although you are getting benefit of path compression.

Upvotes: 2

Related Questions