Изменения

Предположим теперьОчевидным минусом наивной реализации являлось то, что каждый список включает также поле длины списка при слиянии двух множеств, например относительно большого и что из одного элемента, мы пытались обновить указатели для большого числа элементов, хотя гораздо быстрее было бы поменять указатель лишь одному. Отсюда следуют очевидная оптимизация - давайте будем для каждого множества хранить его размер и изменять указатели на представителя всегда добавляем меньший список к большему элементам из "меньшего" списка. Эта оптимизация называется весовой эвристикой и позволяет добиться асимптотики <tex>O(при одинаковых длинах порядок добавления безразличенn \log n)</tex> для n - операций union. При такой простейшей весовой эвристике Хотя одна операция union по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов. Однако последовательность из m операций makeSet, union и findSet, n из которых составляют операции makeSet, требует для выполнения <tex>O(m + n \log n)</tex> времени.