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

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

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

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

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

• [math]\mathrm {insert(set, elem)}[/math] — добавляет заданный элемент [math]elem[/math] в подходящее место множества [math]set[/math] (сохраняя свойство упорядоченности),
• [math]\mathrm {delete(set, elem)}[/math] — удаляет элемент [math]elem[/math] (сохраняя свойство упорядоченности),
• [math]\mathrm {search(set, elem)}[/math] — получает на вход искомое значение элемента [math]elem[/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].

Рассмотрим реализацию на примере отсортированного по возрастанию целочисленного массива.

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

insert

func insert(Set<T> s, T elem):
    int i = 0
    while i < s.n && s.elements[i] < elem            // Ищем индекс первого элемента, большего elem.
        i++
    s.n = s.n + 1                                    // Увеличиваем количество элементов множества на единицу,
    Array.Resize(s.elements, s.n)                    // увеличиваем размер массива с элементами множества на единицу.
    if i != s.n - 1                                  // Если elem не максимальный,
        int j
        for j = s.n - 2 downto i                     // то сдвигаем все элементы массива, большие elem,
            s.elements[j + 1] = s.elements[j]        // на одну позицию вправо.
    s.elements[i] = elem                             // Вставляем elem в нужное место.

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

delete

func delete(Set<T> s, T elem):
    int i = 0                                         // Устанавливаем счетчик на первый элемент.
    while i < s.n && s.elements[i] != elem            // Ищем индекс элемента elem.
        i++
    if i != s.n                                       // Если элемент найден, то
        for j = i to s.n - 2                          // сдвигаем все элементы массива, большие elem,
            s.elements[j] = s.elements[j + 1]         // на одну позицию влево (elem удаляется).
        s.n = s.n - 1                                 // Уменьшаем число элементов массива на единицу.
        Array.Resize(s.elements, s.n)                 // Удаляем дубликат последнего элемента.

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

search

Для нахождения результата используем бинарный поиск.

T search(Set<T> s, T elem):
    if s.elements[0] <= elem && s.elements[s.n] >= elem        // Если элемент elem существует, то
        int i = binSearch(s.elements, elem)                    // ищем индекс элемента elem
        return s.elements[i]                                   // и выводим его значение.
    else                                                       // В противном случае
        return null                                            // возвращаем null.

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

minimum

Первый элемент множества минимальный, так как массив отсортирован по возрастанию.

T minimum(Set<T> s):
    T min = s.elements[0]
    return min

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

maximum

Выполняется аналогично операции [math]\mathrm {minimum(set)}[/math].

T maximum(Set<T> s):
    T max = s.elements[0]
    return max

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

predecessor

Выполняется аналогично операции [math]\mathrm {search(set, elem)}[/math].

T predecessor(Set<T> s, T elem):
    if s.elements[0] < elem && s.elements[s.n] >= elem         // Если элемент elem существует и не равен минимальному,
        int i = binSearch(s.elements, elem)                    // то ищем индекс элемента elem
        return s.elements[i - 1]                               // и выводим предшествующий ему элемент.
    else                                                       // В противном случае
        return null                                            // возвращаем null.

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

successor

Выполняется аналогично операции [math]\mathrm {search(set, elem)}[/math].

T successor(Set<T> s, T elem):
    if s.elements[0] <= elem && s.elements[s.n] > elem         // Если элемент elem существует и не равен максимальному,
        int i = binSearch(s.elements, elem)                    // то ищем индекс элемента elem
        return s.elements[i + 1]                               // и выводим следующий за ним элемент.
    else                                                       // В противном случае
        return null                                            // возвращаем null.

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

Замечания

• В случае, когда упорядоченность элементов коллекции не важна, возможно использование хешей.
• Если задан массив с повторяющимися элементами, то в операциях [math]\mathrm {predecessor(set, elem)}[/math] и [math]\mathrm {successor(set, elem)}[/math] следует использовать левосторонний и правосторонний бинарный поиск соответственно.

Примеры

• Пустое множество [math] \varnothing [/math],
• множество натуральных чисел [math] \mathbb N [/math],
• множество целых чисел [math] \mathbb Z [/math],
• строки, отсортированные в лексикографическом порядке.

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

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