Операции с d-кучей
При реализации основных операций над кучами используются две вспомогательные операции — ВСПЛЫТИЕ и ПОГРУЖЕНИЕ. При реализации этих операций введем еще одну вспомогательную операцию — транспонирование, с помощью которой будем менять местами элементы, расположенные в двух разных узлах дерева. Ее реализация может быть представлена следующим образом:
Замечание.
Если в кучу помещаются только ключи элементов, то процедура транспонирования модифицируется соответствующим образом.
Операция ВСПЛЫТИЕ.Эта операция применяется в тех случаях, когда в некотором узле, например в -м, расположен элемент , нарушающий кучеобразный порядок так, что его ключ меньше ключа его родителя .
Элементы и меняются местами. Если после этого элемент
снова не удовлетворяет условиям кучи, то еще раз проводится аналогичная перестановка. И так до тех пор, пока не встанет на свое место.
Рассмотрим 3-дерево на рис. 4.3. В этом дереве кучеобразный порядок нарушает узел с ключом , так как его родительскому узлу приписан элемент с ключом .
Рис. 4.3.
Применим к узлу операцию ВСПЛЫТИЕ. Элементы с ключами и меняются местами. В результате получается дерево, представленное на рис. 4.4.
Рис. 4.4.
Теперь нарушен кучеобразный порядок в узле (), меняем местами элементы c ключами и . В результате получаем кучу, изображенную на рис. 4.5. Кучеобразный порядок восстановлен, операция ВСПЛЫТИЕ завершена.
Рис. 4.5.
Вычислительная сложность этой операции пропорциональна числу сравнений элементов и их обменов. Это число, очевидно, не более чем удвоенное число узлов в пути от узла до корня дерева. Длина такого пути в -куче с узлами не превосходит ее высоты, а именно , в соответствии с доказанным выше утверждением 1. Значит, время выполнения данной операции — .
Реализация операции ВСПЛЫТИЕ. Входным параметром этой операции является номер узла, в котором нарушен порядок:
Замечание.
- Операцию ВСПЛЫТИЕ можно применять не только к -куче, но и к другим видам куч.
- Для более эффективного выполнения операции ВСПЛЫТИЕ можно поступить следующим образом: запомнить элемент, находящийся в узле , переместить элемент из его родительского узла
в узел , затем из узла в узел
и так до тех пор, пока не освободится узел для запомненного элемента. После этого поместить запомненный элемент на освободившееся место. Более точно это можно выразить с помощью следующих операторов:
Операция ПОГРУЖЕНИЕ. Эта операция также применяется для восстановления свойства кучеобразности. Пусть, например, в -м узле расположен элемент , нарушающий кучеобразный порядок таким образом, что ключ элемента больше ключа элемента , приписанного потомку узла . В этом случае среди непосредственных потомков узла выбирается элемент с наименьшим ключом, и элементы и меняются местами. Если после этого элемент снова не удовлетворяет условиям кучи, то еще раз проводим аналогичную перестановку. И так до тех пор, пока не встанет на свое место.
Рассмотрим -дерево, представленное на рис. 4.6. В узле расположен элемент с ключом , и этот узел имеет двух потомков с меньшими ключами, а именно и . Применим к элементу
операцию ПОГРУЖЕНИЕ.
Рис. 4.6.
Если у узла нет потомков, то .
Реализация операции ПОГРУЖЕНИЕ
Операция ВСТАВКА. Если перед выполнением этой операции куча содержала узлов (напомним, что они пронумерованы числами от
до ), то добавляем к дереву -й узел (его номер будет ) и приписываем ему элемент с именем и ключом . Вставка нового элемента производится посредством отведения для него места в -ых позициях массивов и соответственно, после чего к добавленному узлу применяется операция ВСПЛЫТИЕ для восстановления кучеобразного порядка.
Вставим в -кучу, изображенную на рис. 4.9, новый элемент с ключом .
Рис. 4.9.
Сначала добавляем к дереву новый узел с номером и приписываем ему элемент с ключом . Получим дерево, представленное на рис. 4.10.
Рис. 4.10.
Затем применяем к узлу операцию ВСПЛЫТИЕ. При описании этой операции использовался именно приведенный пример (см. рис. 4.3, 4.4, 4.5).
Вычислительная сложность данной операции равна константе плюс вычислительная сложность операции ВСПЛЫТИЕ, то есть .
Реализация операции ВСТАВКА
Операция УДАЛЕНИЕ.
Используется для удаления элемента, приписанного узлу с заданным номером . Сначала элемент, приписанный последнему узлу дерева, переносится на место удаляемого элемента, последний узел при этом становится ненужным и поэтому удаляется из дерева. Далее, если узел , в который помещен новый элемент, имеет родителя с большим ключом, то к узлу применяется операция ВСПЛЫТИЕ, в противном случае — ПОГРУЖЕНИЕ.
Таким образом, ориентируясь на худший случай, вычислительную сложность операции УДАЛЕНИЕ оцениваем величиной .
Реализация операции УДАЛЕНИЕ
Операция УДАЛЕНИЕ_МИНИМУМА. Эта операция предназначена для взятия из кучи элемента с минимальным ключом (он находится в корне дерева) и удаления его из кучи с помощью операции УДАЛЕНИЕ.
Реализация операции УДАЛЕНИЕ_МИНИМУМА
Функция MINKEY. Эта функция предназначена для определения минимального ключа без удаления соответствующего элемента.
Реализация функции MINKEY
Трудоемкость операции, очевидно, равна .
Операция УМЕНЬШЕНИЕ_КЛЮЧА. Предназначена для уменьшения ключа у элемента, приписанного узлу с заданным номером , на заданную величину .
Это действие может нарушить кучеобразный порядок лишь таким образом, что уменьшенный ключ элемента в узле станет меньше ключа элемента в родительском узле. Для восстановления порядка в куче используется операция ВСПЛЫТИЕ.
Вычислительная сложность данной операции определяется временем, затрачиваемым на уменьшение ключа (то есть константой), и временем выполнения операции ВСПЛЫТИЕ (то есть . В итоге вычислительная сложность операции УМЕНЬШИТЬ_КЛЮЧ равна .
Реализация операции УМЕНЬШЕНИЕ_КЛЮЧА
Операция ОКУЧИВАНИЕ.
Заметим, что если -куча создается путем -кратного применения операции ВСТАВКА, то суммарная трудоемкость ее создания будет равна . Если же все элементов сначала занимают в произвольном порядке массив и, соответственно, массив , то можно превратить их в -кучу, применяя операцию ПОГРУЖЕНИЕ по очереди к узлам .
Такой процесс будем называть окучиванием массива. Для доказательства того, что в результате действительно устанавливается кучеобразный порядок, достаточно заметить, что если поддеревья с корнями в узлах упорядочены по правилу кучи, то после применения процедуры ПОГРУЖЕНИЕ к узлу поддерево с корнем в этом узле также станет упорядоченным по правилу кучи. Итак, остановимся на следующей реализации.
Реализация операции ОКУЧИВАНИЕ
Утверждение 3.
Вычислительная сложность операции ОКУЧИВАНИЕ равна .
Доказательство
Заметим, что трудоемкость погружения с высоты
равна , а количество узлов высоты
не превосходит . Осталось оценить сумму где , и убедиться, что полученная сумма есть .
Для суммирования можно воспользоваться формулой
Предоставляем читателю возможность завершить доказательство.
Операция СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ.
Эта операция применяется для получения списка элементов, которые имеют ключи, меньшие заданного значения , и реализуется следующим образом. Если ключ элемента, находящегося в корне, больше, чем , то это дерево не имеет искомых элементов. В противном случае включаем его в выходной список , а затем применяем ту же процедуру ко всем потомкам узла, включенного в список.
Пусть куча содержит элементов с ключами, меньшими, чем . По свойству кучи, они все расположены на ее "верхушке". Данная процедура обходит эту верхушку за время, пропорциональное , и для каждого из этих элементов просматривает все его (или меньше) непосредственных потомков. Получаем, что время выполнения данной процедуры является величиной .
Реализация операции СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ
Сводные данные о трудоемкости операций с d-кучами
| ВСПЛЫТИЕ | |
| ПОГРУЖЕНИЕ | |
| ВСТАВКА | |
| УДАЛЕНИЕ | |
| УДАЛЕНИЕ_МИН | |
| MINKEY | |
| УМЕНЬШЕНИЕ_КЛЮЧА | |
| ОБРАЗОВАTЬ_ОЧЕРЕДЬ | |
| СПИСОК_МИН |
Для -куч "неудобной" является операция слияния куч.
