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

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

Упорядоченное множество [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].

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

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

int Set[2, n] func initialize():

   for i = 0 to n - 1
       Set[1, i] = i
           Set[2, i] = i + 1

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

func insert(Set, elem, elemKey):

   n = n + 1

A rray.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

Функция delete удаляет элемент, имеющий ключ key (сохраняя свойство упорядоченности).

func delete(Set, key):

   i = 0
   while i < n
       if key == Set[2, i]
           for j = i to n - 2
               Set[1, j] = Set[1, j + 1]
               Set[2, j] = Set[2, j + 1]
       n = n - 1
   Array.Resize(Set[2], n)

Функция search, которая получает на вход искомый ключ key, и возвращает указатель на элемент множества Set или специальное значение null, если такого элемента нет.

int search(Set, key):

   for i = 0 to n - 1
       if Set[2, i] == key
           return Set[1, i]
       else return null

Функция minimum возвращает указатель на минимальный элемент множества Set.

int Minimum(Set):

   return Set[1, 0]

Функция maximum возвращает указатель на максимальный элемент множества Set.

int maximum(Set):

   return Set[1, n - 1]

Функция predecessor возвращает указатель на элемент, стоящий перед элементом elem множества Set.

int predecessor(Set, elem):

   for i = 1 to n - 1
       if elem == Set[1, i]
           return Set[1, i - 1]
       else return null

Функция successor(Set, elem) возвращает указатель на элемент, стоящий после элемента elem множества Set.

int successor(Set, elem):

   for i = 0 to n - 2
       if elem == Set[1, i]
           return Set[1, i + 1]
       else 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 с.