Объединение найти структуру данных

Question

Для многих проблем, которые я вижу, рекомендуется использовать структуру данных union-find. Я пытался прочитать об этом и подумать, как это реализовано (с использованием C++). В настоящее время я понимаю, что это не что иное, как список наборов. Итак, чтобы найти, к какому набору принадлежит элемент, нам нужно n*log n операции. И когда мы должны выполнить объединение, тогда мы должны найти два набора, которые нужно объединить, и сделать set_union на них. Это не выглядит ужасно эффективным для меня. Правильно ли я понимаю эту структуру данных или я что-то упустил?

Answer 1

Это довольно поздний ответ, но, вероятно, на него не было ответа в другом месте в stackru, и, поскольку это самая верхняя страница для тех, кто ищет union-find, вот подробное решение.

Find-Union - очень быстрая операция, выполняемая в почти постоянное время. Это следует из представления Джереми о сжатии пути и отслеживании размеров набора. Сжатие пути выполняется для каждой операции поиска, тем самым занимая амортизированное время lg*(n). lg* подобен обратной функции Аккермана, которая растет настолько медленно, что редко превышает 5 (по крайней мере, до n< 2^65535). Объединение / слияние наборов выполняется лениво, просто указывая один корень на другой, в частности корень меньшего набора на корень большего набора, который выполняется за постоянное время.

См. Приведенный ниже код по https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set%29%20Data%20Structure.cpp

class UF {
  int *id, cnt, *sz;
  public:
// Create an empty union find data structure with N isolated sets.
UF(int N) {
    cnt = N; id = new int[N]; sz = new int[N];
    for (int i = 0; i<N; i++)  id[i] = i, sz[i] = 1; }
~UF() { delete[] id; delete[] sz; }

// Return the id of component corresponding to object p.
int find(int p) {
    int root = p;
    while (root != id[root])    root = id[root];
    while (p != root) { int newp = id[p]; id[p] = root; p = newp; }
    return root;
}
// Replace sets containing x and y with their union.
void merge(int x, int y) {
    int i = find(x); int j = find(y); if (i == j) return;
    // make smaller root point to larger one
    if (sz[i] < sz[j]) { id[i] = j, sz[j] += sz[i]; }
    else { id[j] = i, sz[i] += sz[j]; }
    cnt--;
}
// Are objects x and y in the same set?
bool connected(int x, int y) { return find(x) == find(y); }
// Return the number of disjoint sets.
int count() { return cnt; }
};

Пожалуйста, проголосуйте или примите, если хотите.

Answer 2

Структура данных может быть представлена ​​в виде дерева с перевернутыми ветвями (вместо того, чтобы указывать вниз, ветви указывают вверх на родителя --- и связывают дочерний элемент с его родителем).

Если я правильно помню, это можно показать (легко):

• что сжатие пути (всякий раз, когда вы выполняете поиск "родителя" множества A, вы "сжимаете" путь так, чтобы каждый последующий вызов к ним обеспечивал родителя во времени O(1)), приведет к O(log n сложность за звонок;

• эта балансировка (вы приблизительно отслеживаете количество дочерних элементов в каждом наборе, а когда вам нужно "объединить" два набора, вы делаете тот, у которого меньше дочерних элементов, чем у самого большого), также приводит к O (журнал n) сложность за вызов.

Более сложное доказательство может показать, что когда вы объединяете обе оптимизации, вы получаете среднюю сложность, которая является обратной функцией Аккермана, написанной α(n), и это было основным изобретением Тарьяна для этой структуры.

Позже, как я полагаю, было показано, что для некоторых конкретных моделей использования эта сложность фактически постоянна (хотя для всех практических целей обратное значение для ackermann составляет около 4). Согласно странице Википедии на сайте Union-Find, в 1989 году амортизированная стоимость за операцию любой эквивалентной структуры данных была показана как Ω(α(n)), что доказывает, что текущая реализация является асимптотически оптимальной.

Answer 3

Надлежащая структура данных union-find использует сжатие пути во время каждого поиска. Это амортизирует стоимость, и каждая операция затем пропорциональна обратной функции Аккермана, которая в основном делает ее постоянной (но не совсем).

Если вы реализуете его с нуля, я бы предложил использовать древовидный подход.

Answer 4

Простая структура с объединенным множеством поддерживает массив (element -> set), делая поиск, который устанавливает постоянное время; обновление их амортизируется по времени и конкатенации списков. Не так быстро, как некоторые из вышеперечисленных подходов, но тривиально для программирования и более чем достаточно для улучшения времени выполнения Big-O, скажем, алгоритма минимального связующего дерева Крускала.