Изменения
→Реализация с весовой эвристикой
Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация {{ --- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция union по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций union требует <tex>O(n \log n)</tex> действий.
'''Псевдокод:'''
s[n]
init():
for i = 0 to n - 1:
s[i].set = i
s[i].next = null
s[i].head = s[i]
s[i].tail = s[i] // храним только для представителя
s[i].count = 1
find(x): // подразумевается, что x {{ --- }} ссылка на один из элементов
return x.head.set
union(x, y): // здесь важно, что x и y {{ --- }} представители множеств
if x == y:
return
else:
if x.count > y.count:
swap(x, y)
i = x.tail
while i != null:
i.head = y
i = i.next
x.next = y.tail // соединили списки
y.count += x.count
== Доказательство оценки времени выполнения ==
