data-structures
Структура данных поиска в Union

Вступление

теория

Структуры данных поиска Union предоставляют следующие операции:

• make_sets(n) инициализирует структуру данных на основе объединения с n синглетонами
• find(i) возвращает представитель для набора элементов i
• union(i,j) объединяет множества, содержащие i и j

Мы представляем наше разбиение элементов 0 на n - 1 , сохраняя родительский элемент parent[i] для каждого элемента i который в конечном итоге приводит к представителю множества, содержащего i .
Если сам элемент является представителем, он является его собственным родителем, то есть parent[i] == i .

Таким образом, если мы начнем с одноэлементных множеств, каждый элемент будет его собственным представителем:

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

Давайте посмотрим, как мы можем объединить множества:
Если мы хотим объединить элементы 0 и 1 и элементы 2 и 3, мы можем сделать это, установив родительский элемент от 0 до 1 и установив родительский элемент от 2 до 3:

В этом простом случае необходимо изменить только родительский указатель элементов.
Если мы хотим объединить большие множества, мы всегда должны изменить родительский указатель представителя набора, который должен быть объединен в другой набор: после слияния (0,3) мы установили родительский элемент представителя множества содержащий 0, представителю множества, содержащего 3

Чтобы сделать пример более интересным, давайте теперь слить (4,5), (5,6) и (3,4) :

Последнее, что я хочу представить, это сжатие пути :
Если мы хотим найти представителя набора, нам, возможно, придется обратиться к нескольким родительским указателям, прежде чем обратиться к представителю. Мы могли бы сделать это проще, сохранив представителя для каждого набора непосредственно в своем родительском узле. Мы теряем порядок, в котором мы объединили элементы, но потенциально можем иметь большой прирост времени выполнения. В нашем случае единственными путями, которые не сжаты, являются пути от 0, 4 и 5 до 3:

Основная реализация

Самая основная реализация структуры данных поиска на основе объединения состоит из parent массива, который хранит родительский элемент для каждого элемента структуры. Следуя этим родительским «указателям» для элемента i мы приводим к представителю j = find(i) множества, содержащего i , где имеет место parent[j] = j .

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;  // Parent for every node

public:
    union_find(size_t n) : parent(n) {
        for (size_t i = 0; i < n; ++i)
            parent[i] = i;      // Every element is its own representative
    }

    size_t find(size_t i) const {
        if (parent[i] == i)     // If we already have a representative
            return i;           // return it
        return find(parent[i]); // otherwise return the parent's representative
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi != pj) {        // If the elements are not in the same set: 
            parent[pi] = pj;   // Join the sets by marking pj as pi's parent
        }
    }
};

Усовершенствования: сжатие пути

Если мы выполняем много операций merge в структуре данных объединения, пути, представленные parent указателями, могут быть довольно длинными. Сжатие путей , как уже было описано в части теории, является простым способом смягчения этой проблемы.

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

Таким образом, сжатие пути в основном используется только на небольшой части структуры, особенно путь, по которому мы идем, чтобы найти представителя набора. Это можно сделать, сохранив результат операции find после каждого рекурсивного подкала:

size_t find(size_t i) const {
    if (parent[i] == i)          // If we already have a representative
        return i;                // return it
    parent[i] = find(parent[i]); // path-compress on the way to the representative
    return parent[i];            // and return it
}

Усовершенствования: объединение по размеру

В нашей текущей реализации merge мы всегда выбираем, чтобы левое множество было дочерним элементом правильного набора, не принимая во внимание размер множества. Без этого ограничения пути (без сжатия пути ) от элемента к его представителю могут быть довольно длинными, что приводит к большим временам выполнения при find вызовов.

Другим общим улучшением является объединение по эвристике по размеру , что делает именно то, что он говорит: при слиянии двух наборов мы всегда устанавливаем, что более крупный набор является родителем меньшего набора, что приводит к длине пути не более шаги:

Мы сохраняем дополнительный элемент std::vector<size_t> size в нашем классе, который инициализируется 1 для каждого элемента. При объединении двух наборов более крупный набор становится родителем меньшего набора, и мы суммируем два размера:

private:
    ...
    std::vector<size_t> size;

public:
    union_find(size_t n) : parent(n), size(n, 1) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {            // If the elements are in the same set: 
            return;                // do nothing
        }
        if (size[pi] > size[pj]) { // Swap representatives such that pj
            std::swap(pi, pj);     // represents the larger set
        }
        parent[pi] = pj;           // attach the smaller set to the larger one
        size[pj] += size[pi];      // update the size of the larger set
    }

Усовершенствования: союз по рангу

Другая эвристика, обычно используемая вместо объединения по размеру, - это объединение по эвристике рангов

Его основная идея состоит в том, что на самом деле нам не нужно хранить точный размер наборов, достаточно приблизиться к размеру (в данном случае: примерно логарифм размера набора), чтобы достичь той же скорости, что и объединение по размеру.

Для этого введем понятие ранга множества, которое задается следующим образом:

• Синглтоны имеют ранг 0
• Если два набора с неравным рангом сливаются, множество с большим рангом становится родителем, а ранг остается неизменным.
• Если два набора равного ранга объединены, один из них становится родителем другого (выбор может быть произвольным), его ранг увеличивается.

Одним из преимуществ объединения по рангу является использование пространства: поскольку максимальный ранг увеличивается примерно как , для всех реалистичных размеров ввода ранг может храниться в одном байте (поскольку n < 2^255 ).

Простая реализация объединения по рангу может выглядеть так:

private:
    ...
    std::vector<unsigned char> rank;

public:
    union_find(size_t n) : parent(n), rank(n, 0) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (rank[pi] < rank[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (rank[pi] > rank[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++rank[pi];
        }
    }

Заключительное улучшение: союз по рангу с ограниченным хранением

Хотя в сочетании с сжатием пути объединение по рангу почти достигает постоянных операций времени в структурах данных объединения, существует окончательный трюк, который позволяет нам вообще избавиться от хранилища rank , сохранив ранжирование в заглавных строках parent массив. Он основан на следующих наблюдениях:

• На самом деле нам нужно хранить рейтинг только для представителей , а не для других элементов. Для этих представителей нам не нужно хранить parent .
• Пока что parent[i] не больше size - 1 , т.е. большие значения не используются.
• Все звания не более ,

Это подводит нас к следующему подходу:

• Вместо условия parent[i] == i , мы теперь определяем представителей по
  parent[i] >= size
• Мы используем эти значения вне пределов для хранения рангов множества, т. Е. Множество с представителем i имеет ранг parent[i] - size
• Таким образом, мы инициализируем родительский массив с parent[i] = size вместо parent[i] = i , т. Е. Каждый набор является его собственным представителем с рангом 0.

Поскольку мы смещаем только значения ранга по size , мы можем просто заменить вектор rank parent вектором в реализации merge и только нужно обменивать условие, идентифицирующее представителей в find :

Завершенная реализация с использованием объединения по рангу и сжатию пути:

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;

public:
    union_find(size_t n) : parent(n, n) {} // initialize with parent[i] = n

    size_t find(size_t i) const {
        if (parent[i] >= parent.size()) // If we already have a representative
            return i;                   // return it
        return find(parent[i]);         // otherwise return the parent's repr.
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (parent[pi] < parent[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (parent[pi] > parent[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++parent[pi];
        }
    }
};