В операции объединения, которая лучше на основе ранга или размера, где операция поиска выполняется с использованием сжатия пути

Согласно моему пониманию, объединение по размеру лучше, потому что сжатие пути в операции поиска также изменяет ранг, который не обновляется, тогда как размер остается тем же. Но в некоторых редакционных статьях для задач было выполнено объединение по рангу. Я не понимаю основного различия между ними.

Наборы A и B должны быть объединены

Инициализируется с размером [i]=1 и Arr[i]=i для всех i до n

void union_sizebased(int Arr[ ],int size[ ],int A,int B)
{

 int root_A = root(A);
 int root_B = root(B);

if(size[root_A] < size[root_B ])
{
  Arr[ root_A ] = Arr[root_B];
  size[root_B] += size[root_A];
}

else
{
 Arr[ root_B ] = Arr[root_A];
 size[root_A] += size[root_B];
}

}

Инициализируется с Arr[i]=i и rank[i]=0 для всех i до n

void union_rankbased(int Arr[ ],int rank[ ],int A,int B)
{
int root_A = root(A);
int root_B = root(B);

if(rank[root_A] < rank[root_B ])
{
Arr[ root_A ] = Arr[root_B];
}

else if(rank[root_B] < rank[root_A ]
{
Arr[ root_B ] = Arr[root_A];
}

else 
{
 Arr[root_B]=Arr[root_A];  // Arbitrarly choosing between two and assigning
 rank[root_A]++;
 }
}

0 ответов

Другие вопросы по тегам