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

Определение:

Упорядоченное множество [math]Set[/math] представляет собой коллекцию элементов [math]elem[/math], каждому из которых присваивается определенный ключ [math]key[/math], отвечающий за порядок этого элемента в множестве. Бинарное отношение [math]R[/math] на упорядоченном множестве [math]Set[/math] является отношением порядка.

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

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

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

Insert

Функция [math]\mathrm {insert(Set, elem, elemKey)}[/math] добавляет заданный элемент [math]elem[/math], имеющий ключ [math]elemKey[/math], в подходящее место множества [math]Set[/math] (сохраняя свойство упорядоченности).

Delete

Функция [math]\mathrm {delete(Set, key)}[/math] удаляет элемент, имеющий ключ [math]key[/math] (сохраняя свойство упорядоченности).

Search

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

Minimum

Функция [math]\mathrm {minimum(Set)}[/math] возвращает указатель на минимальный элемент множества [math]Set[/math].

Maximum

Функция [math]\mathrm {maximum(Set)}[/math] возвращает указатель на максимальный элемент множества [math]Set[/math].

Predecessor

Функция [math]\mathrm {predecessor(Set, elem)}[/math] возвращает указатель на элемент, стоящий перед элементом [math]elem[/math] множества [math]Set[/math].

Successor

Функция [math]\mathrm {successor(Set, elem)}[/math] возвращает указатель на элемент, стоящий после элемента [math]elem[/math] множества [math]Set[/math].

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

Пусть [math]Set[/math] — упорядоченное множество (массив), состоящее из [math]n[/math] элементов. В [math]Set[1, i][/math] хранятся элементы множества, в [math]Set[2, i][/math] — их ключи.

Функция [math]\mathrm {insert(Set, elem, elemKey)}[/math]:

func insert(Set, elem, elemKey):
    n = n + 1
    Array.Resize(Set[2], n)
    i = n - 1
    Set[1, i] = Set[1, i - 1]
    Set[2, i] = Set[2, i - 1]
    while elemKey < Set[2, i - 1]
        Set[1, i - 1] = Set[1, i - 2]
        Set[2, i - 1] = Set[2, i - 2]
        i = i - 1
    Set[1, i] = elem
    Set[2, i] = elemKey

Функция [math]\mathrm {delete(Set, key)}[/math]:

func delete(Set, key):
    i = 0
    while Set[2,i] < key && i < n
        i = i + 1
    if i < n
        if i < n - 1
            Set[1, j] = Set[1, j + 1]
            Set[2, j] = Set[2, j + 1]
    n = n - 1
    Array.Resize(Set[2], n)

Функция [math]\mathrm {search(Set, key)}[/math]:

int search(Set, key):
    for i = 0 to n - 1
        if Set[2, i] == key
            return Set[1, i]
    return null

Функция [math]\mathrm {minimum(Set)}[/math]:

int minimum(Set):
    return Set[1, 0]

Функция [math]\mathrm {maximum(Set)}[/math]:

int maximum(Set):
    return Set[1, n - 1]

Функция [math]\mathrm {predecessor(Set, elem)}[/math]:

int predecessor(Set, elem):
    for i = 1 to n - 1
        if elem == Set[1, i]
            return Set[1, i - 1]
    return null

Функция [math]\mathrm {successor(Set, elem)}[/math]:

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

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

Примеры

• Графы;
• Пустое множество [math] \varnothing [/math];
• Множество натуральных чисел [math] \mathbb N [/math].

Литература

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