Изменения

{{Определение|definition ='''Упорядоченное множество''' <tex>Set</tex> (англ. ''ordered set'') представляет собой коллекцию элементов <tex>elem</tex>, каждому из которых присваивается определенный ключ <tex>key</tex>, отвечающий за порядок этого элемента в множестве. Бинарное отношение <tex>R</tex> на упорядоченном множестве <tex>Set</tex> является [[отношение порядка|отношением порядка]].}}''Вполне упорядоченным множеством'', которое явяется важнейшим частным случаем, называется упорядоченное множество, каждое непустое подмножество которого содержит минимальный элемент.

==Операции над '''Вполне упорядоченным множеством==Над упорядоченным множеством <tex>Set</tex> заданы следующие операции:=== Insert ===Функция <tex>\mathrm {insert(Set''', которое явяется важнейшим частным случаем, elemназывается упорядоченное множество, elemKey)}</tex> добавляет заданный каждое непустое подмножество которого содержит минимальный элемент <tex>elem</tex>, имеющий ключ <tex>elemKey</tex>, в подходящее место множества <tex>Set</tex> (сохраняя свойство упорядоченности).

=== Delete =Операции над упорядоченным множеством ==Функция Над упорядоченным множеством <tex>set</tex> заданы следующие операции:* <tex>\mathrm {insert(set, elem)}</tex> {{---}} добавляет заданный элемент <tex>elem</tex> в подходящее место множества <tex>set</tex> (сохраняя свойство упорядоченности),* <tex>\mathrm {delete(Setset, keyelem)}</tex> {{---}} удаляет элемент, имеющий ключ <tex>keyelem</tex> (сохраняя свойство упорядоченности),* <tex>\mathrm {search(set, elem)}</tex> {{---}} получает на вход искомое значение элемента <tex>elem</tex> и возвращает <tex>true</tex> при наличии элемента в множестве или <tex>false</tex> в противном случае,* <tex>\mathrm {minimum(set)}</tex> {{---}} возвращает минимальный элемент множества <tex>set</tex>,* <tex>\mathrm {maximum(set)}</tex> {{---}} возвращает максимальный элемент множества <tex>set</tex>,* <tex>\mathrm {predecessor(set, elem)}</tex> {{---}} возвращает элемент, стоящий перед элементом <tex>elem</tex> множества <tex>set</tex>.* <tex>\mathrm {successor(set, elem)}</tex> {{---}} возвращает элемент, стоящий после элемента <tex>elem</tex> множества <tex>set</tex>.

=== Search =Наивная реализация на массиве ==Функция Упорядоченное множество <tex>\mathrm {search(Set, key)}s</tex>, которая получает на вход искомый ключ содержащее <tex>keyn</tex>элементов, и возвращает указатель на элемент множества <tex>Setможно реализовать с помощью [[Сортировки | отсортированного]] массива </tex> или специальное значение <tex>nullelements[0..n-1]</tex>, если такого элемента нет.

=== Minimum ===Функция <tex>\mathrm {minimum(Set)}</tex> возвращает указатель Рассмотрим реализацию на минимальный элемент множества <tex>Set</tex>примере отсортированного по возрастанию целочисленного массива.

<code> '''struct''' Set<T>: '''int''' n <font color=green>// количество элементов множества</font color== Maximum ===green>Функция '''T'''[n] elements <texfont color=green>\mathrm {maximum(Set)}</tex> возвращает указатель на максимальный элемент / массив элементов множества типа ''T''<tex/font color=green>Set</texcode>.

=== Predecessor '''insert''' ===Функция <texcode>\mathrm {predecessor '''func''' insert(Set<T> s, T elem)}: s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</texfont color=green> <font color=green> возвращает указатель // увеличиваем размер массива с элементами множества на элементединицу.</font color=green> s.elements[s.n - 1] = elem <font color=green>// Вставляем ''elem'' в конец массива</font color=green> '''int''' i = s.n - 1 '''while''' s.elements[i] < s.elements[i - 1] <font color=green>// Сортируем массив,</font color=green> swap(s.elements[i], стоящий перед элементом s.elements[i - 1]) <texfont color=green>// пока ''elem'' не окажется в нужном месте.</font color=green></texcode> множества Время выполнения {{---}} <tex>SetO(n)</tex>.

=== Successor '''delete''' ===Функция <texcode>\mathrm {successor '''func''' delete(Set<T> s, T elem)}: '''int''' i = 0 <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green> '''while''' i < s.n '''and''' s.elements[i] != elem <font color=green>// Ищем индекс элемента ''elem''.</texfont color=green> i++ '''if''' i != s.n <font color=green> возвращает указатель на // Если элементнайден, стоящий после элемента то</font color=green> '''for''' j = i '''to''' s.n - 2 <font color=green>// сдвигаем все элементы массива, большие ''elem'',</font color=green> s.elements[j] = s.elements[j + 1] <texfont color=green>// на одну позицию влево (elemудаляется).</texfont color=green> s.n = s.n - 1 <font color=green>// Уменьшаем число элементов массива на единицу.</font color=green></code> множества Время выполнения {{---}} <tex>SetO(n)</tex>.

==Наивная реализация на массиве= '''search''' ===Пусть Set -- упорядоченное множество (массив), состоящее из n элементов. ВSetДля нахождения результата используем [[1, iЦелочисленный двоичный поиск|бинарный поиск] хранятся элементы множества, в Set[2, i] -- их ключи.

int <code> '''bool''' search(Set[2<T> s, n]func initialize(T elem): for '''int''' i = 0 to n - 1binSearch(s.elements, elem) Set '''return''' s.elements[1, i] = i= elem <font color=green>// Сравниваем найденное значение с искомым...</font color=green></code> Set[2, i] = i + 1Время выполнения {{---}} <tex>O(\log n)</tex>.

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

func insert<code> '''T''' minimum(Set, elem, elemKey<T> s): n '''T''' min = n + 1A rrays.Resize(Setelements[20], n) i = n - 1 '''return''' min Set[1, i] = Set[1, i - 1] Set[2, i] = Set[2, i - 1] while elemKey < Set[2, i - 1]/code> Set[1, i Время выполнения {{- 1] = Set[1, i - 2] Set[2, i - }} <tex>O(1] = Set[2, i - 2] i = i - 1 Set[1, i] = elem Set[2, i] = elemKey)</tex>.

Функция delete удаляет элемент, имеющий ключ key === '''maximum''' ===Выполняется аналогично операции <tex>\mathrm {minimum(сохраняя свойствоупорядоченностиset)}</tex>.

func delete<code> '''T''' maximum(Set, key<T> s): i '''T''' max = 0 while i < n if key == Sets.elements[2, i] for j = i to s.n - 2 Set[1, j] = Set[1, j + 1] Set[2, j] = Set[2, j + 1] '''return''' max</code> n = n Время выполнения {{--- }} <tex>O(1 Array)</tex>.Resize(Set[2], n)

Функция search, которая получает на вход искомый ключ key=== '''successor''' ===В операции используется [[Целочисленный двоичный поиск|правосторонний бинарный поиск]], и возвращаетуказатель на элемент множества Set или специальное значение nullкоторый вернет такое <tex>i</tex>, если такогоэлемента нетчто <tex> s.elements[i - 1]\leqslant elem < s.elements[i] </tex>.

int search<code> '''T''' successor(Set<T> s, keyT elem): for i = 0 to '''if''' elem > s.elements[s.n - 1] <font color=green>// Если элемент больше максимального,</font color=green> '''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green> '''else if Set''' elem < s.elements[20] '''return''' min(s) <font color=green>// Если элемент меньше минимального, возвращаем минимальный элемент.</font color=green> '''int''' i] =binSearch(s.elements, elem) <font color=green>// Иначе ищем элемент, больший ''elem''.</font color= keygreen> '''return Set''' s.elements[1, i] else return null</code>Время выполнения {{---}} <tex>O(\log n)</tex>. Операция <tex>\mathrm{predecessor}</tex> выполняется аналогичным образом.

Функция minimum возвращает указатель на минимальный элемент множества Set== Замечания ==* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].

int Minimum(Set):== Примеры == return Set* Пустое множество <tex> \varnothing </tex>,* множество натуральных чисел <tex> \mathbb N </tex>,* множество целых чисел <tex> \mathbb Z </tex>,* строки, отсортированные в [1, 0[лексикографический порядок|лексикографическом порядке]].

Функция maximum возвращает указатель на максимальный элемент множества Set== Источники информации ==* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5* Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.* Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.* [http://ru.wikipedia.org/wiki/Упорядоченное_множество Википедия — Упорядоченное множество]

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 ==Примеры== * Графы;* Пустое множество <tex> \varnothing </tex>;* Множество натуральных чисел <tex> \mathbb N </tex>. == Литература ==# Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5# Александров П. С. Введение в теорию множеств и общую топологию. — М.: Наука, 1977. — 368 с.# Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств // Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 с.