Эвристика по весу и траектории сжатия

Обычно эвристика по рангу и сжатию пути используется для быстрого выполнения операций со структурой данных с непересекающимися множествами. Каким-то образом я нахожу эвристику по весу и сжатию пути более разумной для меня. Достигает ли следующая реализация того же времени выполнения, что и эвристика по рангу и сжатию пути?

НОТА: ранг, используемый в узле структуры, является неправильным, он относится к числу детей, а не к высоте дерева (обычно это означает ранг)

//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;
}

0

Решение

Вы использовали оба weight а также rank в вашей структуре! Если по weight Вы имеете в виду эвристику взвешенного слияния, это то, что обычно rank для (и rankЯ имею в виду высоту дерева, как вы заметили, а не количество детей).

Отслеживание количества детей не дает никакой оптимизации! Потому что сложность Find является функцией высоты дерева, а не количества дочерних элементов в дереве, в котором находится наш входной узел.

Хотя вы получаете выгоду от сжатия пути.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]