Операция

Число затронутых объектов

Make-set(2;i) Маке-зет(ж2)

1 1

Make-set(s„) Unioni, ж2) Union(s2, ж3) Union(s3, хл)

1 1 2 3

UNlON(a;n i, х

п

)

П - 1

Рис. 22.2 22.3 Время выполнения квадратично зависит от числа операций, раций будет пропорциональна

Весовая эвристика

Простейшая реализация операции Union работает медленно из-за того, что при добавлении длинного списка к короткому приходится присваивать новые значения большому количеству указателей. Дела пойдут лучше, если поступить так: хранить вместе с каждым списком информацию о числе элементов в нём, а при выполнении операции Union добавлять более короткий список в конец более длинного (если длины равны, порядок может быть любым). Такой приём называется весовой эвристикой (weighted-union heuristic). Если объединяемые множества содержат примерно поровну элементов, то большого выигрыша не будет, но в целом, как показывает следующая теорема, мы добиваемся экономии.

Теорема 22-1

Предположим, что система непересекающихся множеств реализована с помощью списков, а в операции Union использована весовая эвристика. Тогда стоимость последовательности из то операций Make-Set, Union и Find-Set, среди которых га операций Make-Set, есть 0{m-\-n lg га) (подразумевается, что первоначально система непересекающихся множеств была пуста).

Доказательство.

Стоимость каждой из операций Make-Set и Find-Set, а также стоимость сравнения размеров, соединения списков и обновления записи о размере множества (все эти действия выполняются при операции Union), есть 0(1), так что суммарная стоимость указанных действий есть О (га).

Остаётся оценить стоимость обновления указателей на начало списка. Для этого мы зафиксируем один из элементов (обозначим

п-1

n + i = ©(га2).

8 = 1

его ж) и проследим, сколько раз у него этот указатель менялся.

Весовая эвристика гарантирует, что представитель меняется, лишь если х входит в меньшее из объединяемых множеств. В этом случае число элементов в множестве, содержащем ж, возрастает по крайней мере вдвое. Поскольку окончательный размер множества, содержащего ж, не превосходит га, количество таких удвоений не превосходит [lg га]. Общее количество элементов равно га, так что суммарная стоимость обновления указателей на начало списка есть

0(га lg га), а общее число операций есть О (то) + О (га lg га). Упражнения

22.2-1

Напишите процедуры Make-Set, Find-Set и Union, используя реализацию с помощью списков и весовую эвристику. Считайте, что каждый элемент ж имеет поля гер[ж] (указатель на представителя), а также last[x] (указатель на последний элемент списка) и вг,ге[ж] (число элементов); два последних поля важны только для элемента, являющегося представителем множества.

22.2-2

Изобразите списки, получающиеся в результате работы приведённой ниже программы, и объясните, какой ответ дадут вызовы Find-Set (если используется представление в виде списков и весовая эвристика).

1for i \gets 1 to 16

2do Make-Set(x i)

3for i \gets 1 to 15 by 2

4do Union(x i, x {i+l>)

5for i \gets 1 to 13 by 4

6do Union(x i, x {i+2})

7Union(x l, x 5)

8Union(x {11}, x {13»

9Union(x l, x {10»

10Find-Set(x 2)

11Find-Set(x 9)

22.2-3

Покажите, что при реализации непересекающихся множеств с помощью списков с весовой эвристикой учетную стоимость операций Make-Set и Find-Set можно считать равной 0(1), а учётную стоимость Union можно считать равной О (lgra).

22.2-4

Укажите точную асимптотическую оценку стоимости последовательности операций рис. 22.3 (если используются списки и весовая эвристика).

22.3 Лес непересекающихся множеств

Для системы непересекающихся множеств существует более эффективная реализация (по сравнению с рассмотренными). Именно,

Рис. 22.4

Рис. 22.3 Рис. 22.4. Лес непересекающихся множеств, а) Деревья, представляющие множества рис. 22.2. Представителями множеств являются элементы с и /. б) Результат операции UNION(e,g).

представим каждое множество корневым деревом, в котором вершинами являются элементы множества, а корень является представителем. Получается лес непересекающихся множеств (disjoint-set forest). Как видно из рисунка (см. рис. 22.4 (а)), каждая вершина указывает на своего родителя, а корень указывает сам на себя. При наивном программировании операций Find-Set и Union такая реализация будет ничуть не лучше списочной; если, однако использовать эвристики «объединения по рангу» и «сжатия путей», то получится самая быстрая (из известных в настоящее время) реализация системы непересекающихся множеств.

Наивные реализации операций выглядят так: Make-Set создает дерево с единственной вершиной, FlND-set(a;) состоит в том, что мы идем от х по стрелкам (указывающим на родителя), пока не дойдем до корня (путь, который мы при этом проходим, называется путь поиска, по-английски find path), a Union состоит в том, что мы заставляем корень одного из деревьев указывать не на самого себя, а на корень другого дерева (рис. 22.46).

Две эвристики

Пока что больших преимуществ (по сравнению со списочной реализацией) не видно: например, в результате п - 1 операции Union может получиться дерево, являющееся цепочкой п вершин. Опишем две эвристики, позволяющих добиться почти линейной оценки времени.

Первая эвристика, называемая объединением по рангу (union by rank), напоминает весовую эвристику в списочной реализации: мы объединяем деревья не как попало, а так, чтобы корень «меньшего» дерева указывал на корень «большего». Выбор «большего» определяется не размером дерева, а специальным параметром -рангом (rank) его корня. Ранг определён для каждой вершины х дерева и в первом приближении может рассматриваться как грубая оценка логарифма числа вершин в поддереве с корнем в х. Точное определение ранга будет дано в следующем разделе.

Вторая эвристика, применяемая в операции Find-Set, называется сжатием путей (path compression). Она заключается в следующем: после того, как путь поиска от вершины к корню пройден, дерево перестраивается: в каждой из вершин пути указатель устанавливается непосредственно на корень (рис. 22.5). При этом ранги остаются прежними.