Как реализовать операцию FindMin (x) для структуры данных union-find? - PullRequest
Новая
       30

Как реализовать операцию FindMin (x) для структуры данных union-find?

0 голосов
/ 04 мая 2019

S представляет собой набор целых чисел от 1 до n.Рассмотрим структуру данных union-find, где - помимо операций union (A, B) и find (x) - вас интересует возвращение минимального элемента множества, к которому принадлежит x.

Предложить структуру данныхэто позволяет вам эффективно реализовывать эти операции и анализировать время выполнения для последовательности m find, p findMin и не более (n - 1) объединений.

Я знаю, что должен каким-то образом отсортировать элементы множествак которому принадлежит x (поэтому я сначала нахожу множество, затем сортирую его, и это должно занять O (nlogn) плюс время, используемое операцией find, которое зависит от структуры данных ...).Стоит ли использовать Union-find со сбалансированными объединениями и сжатием пути?Извините, но я очень растерялся!

1 Ответ

0 голосов
/ 04 мая 2019

Ну, все, что вам нужно сделать, это сохранить минимальный элемент в корне набора disjoin.

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

Таким образом, все операции по-прежнему O (log n) (при использовании сжатия пути или объединения по рангу)

или даже O (inverse_ackerman) (при использовании обеих оптимизаций)

Псевдокод (используется только сжатие пути, поэтому все операции выполняются O (log n)): 

const int N = 10;

int P[N+1]; //stores parent of each set, initially all elements set to -1 to indicate no parent
int Min[N+1];//stores min element of each set

int Find(int u)
{
    return P[u] < 0 ? u : P[u] = Find(P[u]);
}

void Union(int u, int v)
{
    u = Find(u);
    v = Find(v);
    if(u == v)return;
    Min[u] = Min[u] < Min[v] ? Min[u] : Min[v]; 
    P[v] = u; 
}

int FindMin(int u)
{
    return Min[Find(u)];
}
...