1.5 Динамические множества

В программировании часто приходится иметь дело с множествами, меняющимися в процессе выполнения алгоритма. Существуют структуры данных, предназначенные для хранения изменяющихся (динамических, по-английски dynamic) множеств.

Разные алгоритмы используют разные операции. Нередко, например, тре- буется лишь добавлять и удалять элементы в множество, а также проверять, принадлежит ли множеству данный элемент. Структура данных, поддержива- ющая такие операции, называется словарём (dictionary). В других ситуациях могут понадобиться более сложные операции. Например, очереди с приорите- тами, в связи с кучами, разрешают выбирать и удалять наименьший элемент (помимо добавления элементов). Понятно, что выбор реализации динамического множества зависит от того, какие операции с ним нам потребуются.

Обычно элемент динамического множества – это запись, содержащая раз- личные поля. Часто одно из полей рассматривается как ключ (key), предназначенный для идентификации элемента, а остальные поля – как дополнительные данные (satellite data), хранящиеся вместе с ключом. Элемент множества ищется по ключу; когда элемент найден, мы можем прочесть или изменить дополнительную информацию, имеющуюся в этом элементе. Во многих случаях все ключи различны, и тогда множество можно рассматривать как функцию, которая каждому существующему ключу ставит в соответствие некоторую дополнительную информацию.

Многие способы реализации множеств требуют, чтобы вместе с каждым ключом хранились не только дополнительные данные, но и некоторая служебная информация (например, указатели на другие элементы множества).

Часто на множестве ключей имеется естественный линейный порядок (на- пример, ключи могут быть действительными числами или словами, на которых есть лексикографический порядок). В этом случае можно говорить, например, о наименьшем элементе множества или об элементе, непосредственно следующем за данным.

Предполагается, что элементы множества хранятся в некоторой общей области памяти и для каждого элемента имеется указатель, который позволяет получить доступ к этому элементу. Обычно в качестве указателя выступает просто адрес в памяти; если язык программирования этого не предусматривает, указателем может быть индекс в массиве.

Операции над множествами делятся на запросы (queries), не меняющие множества, и операции, меняющие множество (modifying operations). Перечислим типичные операции над множествами.

Таблица 1.3 – Основные операции над динамическими множествами (основные словарные операции)

Операции Successor и Predecessor часто используются и при работе с множествами, в которых ключи различных элементов могут совпадать. При этом разумная реализация гарантирует выполнение различных естественных свойств.

Например, функции Successor и Predecessor взаимно обратны; кроме того, начав с Minimum(S) и применяя функцию Successor, можно осуществить перечисление всех элементов множества в неубывающем порядке.

Стоимость операций над множествами обычно оценивается через размер множеств, к которым они применяются.