Простая структура данных для структуры Union-Find

Возможно, самым простым вариантом реализации структуры данных Union-Find является массив Component, в котором хранится имя множества, содержащего каж- дый элемент. Пусть S — множество, состоящее из n элементов {1, ..., n}.
Мы создаем массив Component размера n, в каждом элементе которого Component^] хранится имя множества, содержащего 5. Чтобы реализовать операцию MakeUnionFind(S), мы создаем массив и инициализируем его элементы Component [5] = 5 для всех 5 S. Эта реализация упрощает Find(v): все сводится к простой выборке по ключу, зани- мающей время О(1). Однако операция Union(А, B) для двух множеств A и B может занимать время до O(n) из-за необходимости обновления значений Component[5] для всех элементов множеств A и B.

Чтобы улучшить эту границу, мы проведем несколько простых оптимизаций. Во-первых, будет полезно явно хранить список элементов каждого множества, чтобы для нахождения обновляемых элементов не пришлось просматривать весь массив. Кроме того, можно сэкономить немного времени, выбирая в качестве имени объединения имя одного из исходных множеств, скажем A: в этом случае достаточно обновить значения Component^] для 5

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Простая структура данных для структуры Union-Find:

  1. Упражнение для выявления структуры вашего характера
  2. Жизненная задача и высшее «Я» для оральной структуры
  3. КРИТЕРИИ ОЦЕНКИ ПРОИЗВЕДЕНИЯ с ТОЧКИ ЗРЕНИЯ его ЖАНРОВО–ТЕМАТИЧЕСКОЙ СТРУКТУРЫ и ЗРИТЕЛЬСКОГО ВОСПРИЯТИЯ (для исследователей экранной продукции)
  4. 5.2.17. Укрепления благосостояния своих лучших сотрудников для увеличения функциональности всех элементов, составляющих структуру и архитектуру цели
  5. СТРУКТУРА
  6. § 3. О структуре сознания
  7. Структура
  8. Функциональные структуры.
  9. § 2. Структура парламентов
  10. Свободные структуры
  11. Структура преступной группы
  12. § 2. Психологическая структура личности
  13. ИНТЕЛЛЕКТ: СТРУКТУРА
  14. Линейно-функциональные структуры.
  15. Линейные структуры.
  16. Типы социальных структур
  17. IV. 2. 2. Кольцевые структуры.
  18. Структура юридической социологии.
  19. СТРУКТУРА ЗАМЕТКИ
  20. Глава 3 ВНУТРЕННЯЯ СТРУКТУРА ОРГАНИЗАЦИИ