Изменения

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