Упорядоченное множество

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

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

Операции над упорядоченным множеством

Над упорядоченным множеством [math]Set[/math] заданы следующие операции:

• [math]\mathrm {insert(Set, elem, key)}[/math] — добавляет заданный элемент [math]elem[/math], имеющий ключ [math]key[/math], в подходящее место множества [math]Set[/math] (сохраняя свойство упорядоченности),
• [math]\mathrm {delete(Set, key)}[/math] — удаляет элемент, имеющий ключ [math]key[/math] (сохраняя свойство упорядоченности),
• [math]\mathrm {search(Set, key)}[/math] — получает на вход искомый ключ [math]key[/math] и возвращает указатель на элемент множества [math]Set[/math] или специальное значение [math]null[/math], если такого элемента нет,
• [math]\mathrm {minimum(Set)}[/math] — возвращает указатель на минимальный элемент множества [math]Set[/math],
• [math]\mathrm {maximum(Set)}[/math] — возвращает указатель на максимальный элемент множества [math]Set[/math],
• [math]\mathrm {predecessor(Set, elem)}[/math] — возвращает указатель на элемент, стоящий перед элементом [math]elem[/math] множества [math]Set[/math].
• [math]\mathrm {successor(Set, elem)}[/math] — возвращает указатель на элемент, стоящий после элемента [math]elem[/math] множества [math]Set[/math].

Наивная реализация на массиве

Упорядоченное множество [math]Set[/math], содержащее [math]n[/math] элементов, можно реализовать с помощью массива [math]elements[0..n-1][/math]. Оно будет обладать следующими полями:

• [math]elem[/math] — элемент множества,
• [math]key[/math] — ключ элемента.

struct Set<T>
  int n                            // количество элементов множества
  T[] elements                     // массив элементов множества типа T

insert

func insert(Set, elem, key):
    Set.n = Set.n + 1                     //Увеличиваем размер массива на единицу
    Set.elements[key] = elem              //и добавляем элемент с ключом key.

Время выполнения — [math]O(1)[/math].

delete

func delete(Set, key):
    if key < Set.n - 1                                //Если key — не последний элемент,
        for i = key to Set.n - 2                      //то сдвигаем все элементы множества, начиная с key, влево.
            Set.elements[i] = Set.elements[i + 1]
        Set.n = Set.n - 1                             //Затем удаляем последний элемент (уменьшаем количество элементов множества на единицу).

Время выполнения — [math]O(n)[/math].

search

T search(Set, key):
    for i = 0 to Set.n - 1
        if i == key                                //Если элемент с ключом key существует, возвращаем указатель на него,
            return *(Set.elements + key)
    return null                                    //в противном случае возвращаем null.

Время выполнения — [math]O(n)[/math].

minimum

T minimum(Set):
    T min = Set.elements[0]               //Принимаем первый элемент множества за минимальный.
    int res = 0
    for i = 1 to Set.n - 1
        if min > Set.elements[i]          //Если есть элементы меньше min,
            min = Set.elements[i]         //то записывает элемент в min
            res = i                       //и его ключ в res.
    return *(Set.elements + key)

Время выполнения — [math]O(n)[/math].

maximum

T maximum(Set):
    T max = Set.elements[0]               //Принимаем первый элемент множества за максимальный.
    int res = 0
    for i = 1 to Set.n - 1
        if max < Set.elements[i]          //Если есть элементы больше max,
            max = Set.elements[i]         //то записывает элемент в max
            res = i                       //и его ключ в res.
    return *(Set.elements + key)

Время выполнения — [math]O(n)[/math].

predecessor

T predecessor(Set, elem):
    for i = 1 to Set.n - 1
        if elem == Set.elements[i]
            return *(Set.elements + i - 1)
    return null

Время выполнения — [math]O(n)[/math].

successor

T successor(Set, elem):
    for i = 0 to Set.n - 2
        if elem == Set.elements[i]
            return *(Set.elements + i + 1)
    return null

Время выполнения — [math]O(n)[/math].

В случае, когда упорядоченность элементов коллекции не важна, возможно использование хешей.

Примеры

• Простые приверы множеств:
  • {1, 2, 3, ...},
  • {..., 3, 2, 1},
  • {1, 3, 5, ..., 2, 4, 6, ...},
  • {1, 3, 5, ..., 6, 4, 2},
  • {..., 5, 3, 1, 2, 4, 6, ...},
  • {..., 5, 3, 1, ..., 6, 4, 2},
• пустое множество [math] \varnothing [/math],
• множество натуральных чисел [math] \mathbb N [/math],
• файлы в директории, отсортированные в алфавитном порядке.

Источники информации

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5
• Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.
• Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.

Ссылки

• Упорядоченное множество — Википедия