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

Упорядоченное множество (англ. 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]. Рассмотрим реализацию на примере следующего множества: {0, 2, 4, ..., 5, 3, 1}.

struct set<T>:
  int even                         // количество четных элементов множества
  int odd                          // количество нечетных элементов множества
  int n = even + odd               // общее количество элементов множества
  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(1)[/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]               // Принимаем первый элемент множества за минимальный.
    int i
    for i = 1 to s.n - 1
        if min > s.elements[i]          // Ищем минимальный элемент множества
            min = s.elements[i]
    return min                          // и выводим его.

Время выполнения — [math]O(n)[/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].

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

Примеры

• Простые примеры множеств:
  • {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 с.
• Упорядоченное множество — Википедия