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

Упорядоченное множество (англ. 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):
    s.n = s.n + 1                                 // Увеличиваем количество элементов множества на единицу,
    Array.Resize(s.elements, s.n)                 // увеличиваем размер массива с элементами множества на единицу.
    if elem % 2 == 0                              // Если элемент elem четный, то,
        int i = 0                                 // ставим счетчик элементов массива на первый элемент,
        while elem > s.elements[i]                // увеличиваем счетчик до тех пор, пока не найдем первый элемент, больший elem,
            i = i + 1
        for j = s.n - 1 downto i+1                // сдвигаем все элементы, большие elem, на единицу вправо,
            s.elements[j] = s.elements[j - 1]
        s.elements[i] = elem                      // вставляем элемент elem в ту ячейку массива, на которую указывает счетчик,
        s.even = s.even + 1                       // увеличиваем количество четных элементов на единицу.
    else                                          // Если элемент elem нечетный, то,
        int i = s.even                            // устанавливаем счетчик на первый нечетный элемент,
        while elem < s.elements[i]                // увеличиваем счетчик до тех пор, пока не найдем первый элемент, меньший elem,
            i = i + 1
        for j = s.n - 1 downto i+1                // сдвигаем все элементы, большие elem, на единицу вправо,
            s.elements[j] = s.elements[j - 1]
        s.elements[i] = elem                      // вставляем элемент elem в ту ячейку массива, на которую указывает счетчик,
        s.odd = s.odd + 1                         // увеличиваем количество нечетных элементов на единицу.

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

delete

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

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

search

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

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

minimum

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

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

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

maximum

T maximum(Set<T> s):
    T max = s.elements[0]               // Принимаем первый элемент множества за максимальный.
    int i
    for i = 1 to s.n - 1
        if max < s.elements[i]          // Ищем максимальный элемент множества
            max = s.elements[i]
    return max                          // и выводим его.

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

predecessor

T predecessor(Set<T> s, T elem):
    int i
    for i = 1 to s.n - 1
        if elem == s.elements[i]         // Если в массиве находим елемент elem,
            return s.elements[i - 1]     // то выводим предшествующий ему элемент.
    return null                          // Иначе выводим null.

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

successor

T successor(Set<T> s, T elem):
    int i
    for i = 1 to s.n - 1
        if elem == s.elements[i]         // Если в массиве находим елемент elem,
            return s.elements[i + 1]     // то выводим следующий за ним элемент.
    return null                          // Иначе выводим null.

Время выполнения — [math]O(n)[/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 с.
• Википедия — Упорядоченное множество