Простая структура данных для структуры Union-Find

Возможно, самым простым вариантом реализации структуры данных Union-Find является массив Component, в котором хранится имя множества, содержащего каждый элемент. Пусть S — множество, состоящее из n элементов {1, …, n}.

Мы создаем массив Component размера n, в каждом элементе которого Component[s] хранится имя множества, содержащего s. Чтобы реализовать операцию MakeUnionFind(S), мы создаем массив и инициализируем его элементы Component[s] = s для всех s Ѯ S.

Чтобы улучшить эту границу, мы проведем несколько простых оптимизаций. Во-первых, будет полезно явно хранить список элементов каждого множества, чтобы для нахождения обновляемых элементов не пришлось просматривать весь массив.

Кроме того, можно сэкономить немного времени, выбирая в качестве имени объединения имя одного из исходных множеств, скажем A: в этом случае достаточно обновить значения Component[s] для s Ѯ B, но не для любых s Ѯ A.

Конечно, при большом множестве B выигрыш от этой идеи будет невелик, поэтому мы добавляем еще одну оптимизацию: для большого множества B будет сохраняться его имя, а значения Component[s] будут изменяться для s Ѯ A.

В более общей формулировке хранится дополнительный массив size размера n, где size[A] содержит размер множества A, а при выполнении операции Union(A, B) для объединения используется имя большего множества.

Такой подход сокращает количество элементов, для которых требуется обновить значение Component.

Даже с такими оптимизациями операция Union в худшем случае выполняется за время O(n): это происходит при объединении двух больших множеств A и B, содержащих одинаковые доли всех элементов.

Тем не менее подобные плохие случаи не могут встречаться очень часто, поскольку итоговое множество A Ґ B имеет еще больший размер.

Как точнее сформулировать это утверждение? Вместо того чтобы ограничивать время выполнения одной операции Union для худшего случая, мы можем ограничить общее (или среднее) время выполнения серии из k операций Union.

(4.23) Имеется реализация структуры данных Union-Find на базе массива для некоторого множества S размера n; за объединением сохраняется имя большего множества.

Операция Find выполняется за время O(1), MakeUnionFind(S) — за время O(n), а любая последовательность из k операций Union выполняется за время не более O(k log k).