Структура данных

Структура данных ЛЕКЦИЯ 7 А.Асланян hayk.aslanian@gmail.com Структуры данных для непересекающихся множеств  В некоторых приложениях выполняется группировка различных элементов в набор непересекающихся множеств  Операции  Make-Set – создание множества  Find-Set – поиск множества, содержащий заданных элемент  Union – объединение двух множеств 2 Структуры данных для непересекающихся множеств  Структуры данных для непересекающихся множеств поддерживает набор 𝑆 = {𝑆1 , 𝑆2 , … , 𝑆𝑘 } непересекающихся множеств  Каждое множество - 𝑆𝑖 идентифицируется представителем, который представляет собой некоторый член множества  В одних приложениях не имеет значения, какой именно элемент множества используется в качестве представителя  Главное - запрос представителя множества работал детерминировано   Если множество не изменился, то всегда возвращается один и тот же элемент В других приложениях может действовать предопределенное правило выбора представителя  Например наименьшего члена множества 3 Структуры данных для непересекающихся множеств  Каждый элемент множества представляет некоторый объект 𝑥. Поддерживаются следующие операции  Make-Set (𝒙) – создает новое множество, состоящее из одного члена  Этот элемент и является его представителем  Требуется, чтобы 𝑥 не входил ни в какое иное множество 4  Find-Set (𝒙) – возвращает указатель на представителя множества, в котором содержится элемент 𝑥  Union (𝒙, 𝒚) – объединяет множества, которые содержат 𝑥 и 𝑦 (𝑆𝑥 и 𝑆𝑦 ) и уничтожает 𝑆𝑥 и 𝑆𝑦  Предполагается, что до выполнения операции указанные множества не пересекались  Представителем объединенного множества является элемент из 𝑆𝑥 ∪ 𝑆𝑦  Часто выбирают представителем объединенного множества представителя 𝑆𝑥 или 𝑆𝑦 Структуры данных для непересекающихся множеств  Мы проанализируем зависимость времени работы структуры данных для непересекающихся множеств от двух параметров  Количество операций Make-Set - n  Количество общего количеств операций Make-Set, Union, Find-Set – m  m≥n  Каждая операция Union уменьшает количество множеств на 1  После n-1 операций Union, останется одно множество  Следовательно, количество операций Union не может превышать n-1 5 Структуры данных для непересекающихся множеств  Одно из многих применений – в задаче определении связных компонентов графа 6 Структуры данных для непересекающихся множеств  Используется в алгоритме Краскала для поиска минимального остовного дерева графа 7 Структуры данных для непересекающихся множеств  Мы рассмотрим два метода представления непересекающихся множеств  С помощью связанных списков  С помощью лесов непересекающихся множеств 8 Представление непересекающихся множеств с помощью связанных списков  Каждое множество представлено своим связанным списком  Объект каждого множества имеет 2 атрибута   ℎ𝑒𝑎𝑑 – указывает на первый объект списка  𝑡𝑎𝑖𝑙 указывает на последний объект списка Каждый объект списка содержит  Член множества (f, g, d)  Указатель на следующий объект в списке  Указатель на объект множества 9 Представление непересекающихся множеств с помощью связанных списков  Объекты в пределах каждого списка могут располагаться в любом порядке  Представителем множества является член в первом объекте списка 10 Представление непересекающихся множеств с помощью связанных списков   При использовании представления в виде связанных списков процедуры Make-Set и Find-Set легко реализуются  Процедура Make-Set(𝑥) создает новый связанный список с единственным объектом 𝑥  Find-Set(𝑥) следует по указателю на объект множества и возвращает член объекта, на который указывает ℎ𝑒𝑎𝑑 Время работы обеих процедур равно 𝑂(1) 11 Представление непересекающихся множеств с помощью связанных списков  Union(x,y) добавляет список с элементом x в конец списка, содержащего y  Представителем становится представитель списка содержащий x  Нужно уничтожить старое множество содержащий y  Нужно обновить указатели 12 Представление непересекающихся множеств с помощью связанных списков  Можно построить последовательность из 𝑚 операций над 𝑛 объектами, которая требует Θ(𝑛2 ) времени  Выполняем 𝑛 операции Make-Set - Θ(𝑛)  𝑛 − 1 операции Union - 𝑛−1 𝑖=0 𝑖 = Θ(𝑛2 ) 13 Представление непересекающихся множеств с помощью связанных списков  В наихудшем случае представленная реализации процедуры Union требует Θ(𝑛) времени на один вызов  Если мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка  Мы можем в каждом списке сохранить ее длину и мы всегда добавляем меньший список к большему – весовая эвристика  При одинаковых длинах порядок добавления не имеет значения  Если оба множества имеют по Ω(𝑛) членов, то Union может потребовать Ω(𝑛) времени  Однако, если последовательность из 𝑚 операций Union, Find-Set и Make-Set (𝑛 раз), требует для выполнения 𝑂(𝑚 + 𝑛𝑙𝑔𝑛) 14 Представление непересекающихся множеств с помощью связанных списков  Последовательность из 𝑚 операций Union, Find-Set и Make-Set (𝑛 раз), требует для выполнения 𝑂(𝑚 + 𝑛𝑙𝑔𝑛)  Поскольку каждая операция Union объединяет два непересекающихся множества, всего выполняется не более чем 𝑛 − 1 операций Union  Вычислим верхнюю границу количества обновлений указателей на объект множества для каждого из 𝑛 элементов  Рассмотрим конкретный объект 𝑥  Когда происходит обновление указателя в объекте 𝑥, он должен находиться в меньшем из объединяемых множеств 15 Представление непересекающихся множеств с помощью связанных списков  Когда происходит первое обновление указателя в объекте 𝑥, образованное в результате множество содержит не менее двух элементов  При следующем обновлении указателя на представителя в объекте 𝑥 полученное после объединения множество содержит не менее четырех членов  Продолжая рассуждения, приходим к выводу о том, что для произвольного 𝑘 ≤ 𝑛 после того как указатель в объекте 𝑥 был обновлен 𝑙𝑔𝑘 раз, полученное в результате множество должно иметь не менее 𝑘 элементов  Поскольку имеем 𝑛 элементов, во всех операциях Union указатель каждого объекта может быть обновлен не более 𝑙𝑔𝑛 раз  Для обновления указателей 𝑡𝑎𝑖𝑙 и длин списков, требуется Θ(1) времени  Для обновления 𝑛 объектов требуется 𝑂(𝑛𝑙𝑔𝑛) времени  Каждая операция Make-Set и Find-Set занимает время 𝑂(1)  Полное время выполнения всех операций - 𝑶(𝒎 + 𝒏𝒍𝒈𝒏) 16 17 Леса непересекающихся множеств   Мы представим непересекающиеся множества в виде корневых деревьев  Каждый узел содержит один член множества  Каждое дерево представляет одно множество  Каждый член указывает только на родительский узел  Корень каждого дерева содержит представителя и является родительским узлом для самого себя Далее мы применим две эвристики, что позволит достичь асимптотически оптимального выполнения операций 18 Леса непересекающихся множеств  Make-Set просто создает дерево с одним узлом  Find-Set выполняется перемещением до корня дерева по указателям на родительские узлы   Посещенные узлы на этом простом пути составляют путь поиска Операция Union состоит в том, что корень одного дерева указывает на корень другого Леса непересекающихся множеств эвристики  Пока что у нас нет никаких особых преимуществ перед реализацией с использованием связанных списков  Мы воспользуемся двумя эвристиками   Объединение по рангу  Сжатие пути Применение эвристик позволяет достичь практически линейного времени работы от общего количества операций 𝑚 19 20 Объединение по рангу  Суть эвристики объединения по рангу заключается в том, чтобы корень дерева с меньшим количеством узлов указывал на корень дерева с большим количеством узлов  Также, можно использовать ранг каждого корня, который представляет собой верхнюю границу высоты узла  При выполнении операции Union корень с меньшим рангом должен указывать на корень с большим рангом 21 Объединение по рангу  При создании множества процедурой Make-Set начальный ранг узла ровен 0  Find-Set оставляет ранги неизменными  Процедура Union работает следующим образом  Если ранги деревьев разные, мы делаем корень с большим рангом родительским узлом по отношению к корню с меньшим рангом, но сами ранги остаются неизменными  Если корни имеют одинаковые ранги, то мы произвольным образом выбираем один из корней в качестве родительского и увеличиваем его ранг 22 Сжатие пути  Вторая эвристика – сжатие пути используется в процессе выполнения операции Find-Set и делает каждый узел указывающим непосредственно на корень  Процедура Find-Set является двухпроходной   Первый подход – поиск пути к корню дерева  Второй подход – обновление узлов по найденному пути, которые теперь указывают на корень дерева Сжатие пути не изменяет ранги узлов 23 Сжатие пути  Пример, Find-Set(a) 24 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8) 25 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1,2) 26 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3) 27 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5) 28 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5)  Find-Set(1) 29 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5)  Find-Set(1) 30 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5)  Find-Set(1)  Union(1, 4) 31 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5)  Find-Set(1)  Union(1, 4)  Find-Set(4) 32 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5)  Find-Set(1)  Union(1, 4)  Find-Set(4)  Union(6, 7) 33 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5)  Find-Set(1)  Union(1, 4)  Find-Set(4)  Union(6, 7)  Union(6, 8) 34 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5)  Find-Set(1)  Union(1, 4)  Find-Set(4)  Union(6, 7)  Union(6, 8)  Union(2, 7) 35 Пример  Make-Set (0), Make-Set (1), …, Make-Set (8)  Union(1, 2)  Union(2, 3)  Union(4, 5)  Find-Set(1)  Union(1, 4)  Find-Set(4)  Union(6, 7)  Union(6, 8)  Union(2, 7)  Find-Set(8) 36 Влияние эвристик на время работы  Если применить эвристики раздельно, они повышают эффективность операций   Объединение по рангу дает время работы 𝑶(𝒎 𝒍𝒈𝒏) для всех операций Еще большую эффективность обеспечивает совместное применение  Время работы в наихудшем случае - 𝑂(𝑚 𝛼(𝑛)), где 𝛼(𝑛) – очень медленно растущая функция 37 Влияние эвристик на время работы  Определим 𝐴𝑘 (𝑗) для целых 𝑘 ≥ 0, 𝑗 ≥ 1 𝑗 + 1, если 𝑘 = 0 𝐴𝑘 𝑗 = 𝑗+1 𝐴𝑘−1 𝑗 , если 𝑘 ≥ 1  𝐴𝑘−1 𝑗 − 𝐴𝑘−1  Функция 𝐴𝑘 (𝑗) – строго возрастающая по 𝑗 и 𝑘 𝑖 𝑗+1 𝑖−1 𝐴𝑘−1 𝑗 , для 𝑖 ≥ 1  Для любого целого 𝑗 ≥ 1 𝐴1 𝑗 = 2𝑗 + 1  Для любого целого 𝑗 ≥ 1 𝐴2 𝑗 = 2𝑗+1 𝑗 + 1 − 1 38 Влияние эвристик на время работы  Определим 𝛼 𝑛 обратную к 𝐴𝑘 𝑛 для 𝑛 ≥ 0 𝛼 𝑛 = min 𝑘 ∶ 𝐴𝑘 1 ≥ 𝑛 1  𝛼 𝑛 = 2 3 4 для 0 ≤ 𝑛 ≤ 2, для 𝑛 = 3, для 4 ≤ 𝑛 ≤ 7, для 8 ≤ 𝑛 ≤ 2047, для 2018 ≤ 𝑛 ≤ 𝐴4 𝑘  Только для сверхбольших 𝑛, 𝛼 𝑛 больше 4  Для всех практических применений 𝛼 𝑛 ≤ 4