Изменения
→Наивная реализация на массиве
'''struct''' Set<T>:
'''int''' n <font color=green>// количество элементов множества</font color=green>
'''T'''[n] elements <font color=green>// массив элементов множества типа ''T''</font color=green>
</code>
'''func''' insert(Set<T> s, T elem):
'''int''' i = 0
'''while''' i < s.n '''&&''' s.elements[i] < elem <font color=green>// Ищем индекс первого элемента, большего ''elem''.</font color=green>
i++
s.n = s.n + 1 <font color=green>// Увеличиваем количество элементов множества на единицу,</font color=green>
Array.Resize(s.elements, s.n) <font color=green>// увеличиваем размер массива с элементами множества на единицу.</font color=green>
'''if''' i != s.n - 1 <font color=green>// Если ''elem '' не максимальный,</font color=green>
'''int''' j
'''for''' j = s.n - 2 '''downto''' i <font color=green>// то сдвигаем все элементы массива, большие ''elem'',</font color=green>
s.elements[j + 1] = s.elements[j] <font color=green>// на одну позицию вправо.</font color=green>
s.elements[i] = elem <font color=green>// Вставляем ''elem '' в нужное место.</font color=green>
</code>
Время выполнения {{---}} <tex>O(n)</tex>.
'''func''' delete(Set<T> s, T elem):
'''int''' i = 0 <font color=green>// Устанавливаем счетчик на первый элемент.</font color=green>
'''while''' i < s.n '''&&''' s.elements[i] != elem <font color=green>// Ищем индекс элемента ''elem''.</font 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] <font color=green>// на одну позицию влево (elem удаляется).</font color=green>
s.n = s.n - 1 <font color=green>// Уменьшаем число элементов массива на единицу.</font color=green>
=== '''minimum''' ===
Первый элемент множества минимальный, так как массив отсортирован по неубываниювозрастанию.
<code>
=== '''predecessor''' ===
Выполняется аналогично операции <tex>\mathrm {search(set, elem)}</tex>.
<code>
'''T''' predecessor(Set<T> s, T elem):
'''if''' s.elements[0] < elem '''&&''' s.elements[s.n] >= elem <font color=green>// Если элемент ''elem '' существует и не равен минимальному,</font color=green> '''int''' i = binSearch(s.elements, elem) <font color=green>// то ищем индекс элемента ''elem''</font color=green>
'''return''' s.elements[i - 1] <font color=green>// и выводим предшествующий ему элемент.</font color=green>
'''else''' <font color=green>// В противном случае</font color=green>
'''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green>
</code>
Время выполнения {{---}} <tex>O(log \ n)</tex>.
=== '''successor''' ===
Выполняется аналогично операции <tex>\mathrm {search(set, elem)}</tex>.
<code>
'''T''' successor(Set<T> s, T elem):
'''if''' s.elements[0] <= elem '''&&''' s.elements[s.n] > elem <font color=green>// Если элемент ''elem '' существует и не равен максимальному,</font color=green> '''int''' i = binSearch(s.elements, elem) <font color=green>// то ищем индекс элемента ''elem''</font color=green>
'''return''' s.elements[i + 1] <font color=green>// и выводим следующий за ним элемент.</font color=green>
'''else''' <font color=green>// В противном случае</font color=green>
'''return''' ''null'' <font color=green>// возвращаем ''null''.</font color=green>
</code>
Время выполнения {{---}} <tex>O(log\ n)</tex>.
== Замечания ==* В случае, когда упорядоченность элементов коллекции не важна, возможно использование [[Хеш-таблица|''хешей'']].* Если задан массив с повторяющимися элементами, то в операциях <tex>\mathrm {predecessor(set, elem)}</tex> и <tex>\mathrm {successor(set, elem)}</tex> следует использовать левосторонний и правосторонний бинарный поиск соответственно.
== Примеры ==
