СНМ (списки с весовой эвристикой)

Весовая эвристика (weighted-union heuristic) — улучшение наивной реализации СНМ на списках с указателями на представителя. Позволяет добиться улучшения асимптотики с $O(n^2)$ до $O(n \log n)$ благодаря добавлению меньшего списка к большему при объединении множеств.

Проблема наивной реализации

Рассмотрим реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списка будем хранить указатель на представителя и на следующий элемент в списке.

При такой реализации операция $\mathrm {init}$ для создания n множеств состоящих из одного элемента займет $O(n)$ времени. Для выполнения операции $\mathrm {findSet}$ достаточно перейти по ссылке на представителя за $O(1)$. Узким местом такой реализации является операция $\mathrm {union}$. Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.

Нетрудно придумать последовательность из $n - 1$ операций $\mathrm {union}$, требующую $O(n^2)$ времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку $i$-ая операция $\mathrm {union}$ обновляет $i$ указателей, общее количество указателей, обновленных всеми $n - 1$ операциями $\mathrm {union}$ равно $\sum\limits_{i=1}^{n-1} i = O(n^2)$. Отсюда следует, что амортизированное время выполнения операции $\mathrm {union}$ составляет $O(n)$.

Реализация с весовой эвристикой

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

Псевдокод:

s[n]
function 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  // храним только для представителя

T find(x): // подразумевается, что x — ссылка на один из элементов
  return x.head.set

function union(x, y): 
  x = x.head
  y = y.head
  if x == y
    return
  else
    if x.count > y.count
      swap(x, y)
    i = x.head
    while i != null
      i.head = y
      i = i.next
    y.tail.next = x.head // соединили списки
    y.tail = x.tail 
    y.count += x.count

Доказательство оценки времени выполнения

Утверждение:

При реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции $\mathrm {init}$ для n элементов и m операций $\mathrm {union}$ и $\mathrm {findSet}$, требует для выполнения $O(m+n \log n)$ действий.

$\triangleright$

Оценим время работы необходимое для обновления указателей на представителя в операциях $\mathrm {union}$. Рассмотрим количество обновлений отдельно для каждого элемента. Оказывается, что для каждого элемента мы можем обновить указатель не более $O(\log n)$ раз. Это связано с тем, что при каждом объединении, множество, в котором оказывается объект, увеличивается не менее чем вдвое. Действительно, так как мы обновляем указатель на представителя элементу, то этот элемент находился в меньшем из множеств (согласно нашей эвристике), но тогда размер второго множества не меньше. Тогда после первого обновления элемент содержится в множестве, в котором не менее двух элементов, после второго — четырех, и так далее. В силу того, что множество не может содержать более n элементов, количество обновлений не превосходит $O(\log n)$. Таким образом, общее время, необходимое для обновления указателей для n элементов, составляет $O(n \log n)$. Необходимо также отметить, что слить два списка и обновить поле длины при выполнении $\mathrm {union}$ можно за константное количество операций (последние три строчки в псевдокоде). Отсюда легко понять, что время необходимое для выполнения всей последовательности операций составит $O(m + n \log n)$. Операция $\mathrm {init}$ за $O(n)$, $O(m)$ операций $\mathrm {findSet}$ и часть работы операции $\mathrm {union}$ на обновление поля длины и слияния списков, каждая из которых выполняется за константное время, а также суммарное время обновления указателей на представителя операцией $\mathrm {union}$ для каждого элемента за $O(n \log n)$ действий.

$\triangleleft$

Другие реализации

• СНМ(наивные реализации)
• СНМ(реализация с помощью леса корневых деревьев)

Ссылки

• habrahabr.ru - Система непересекающихся множеств и её применения
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 585—588. — ISBN 5-8489-0857-4