Структуры данных и модели вычислений
и так до тех пор,
в узел , затем из узла в узел
и так до тех пор, пока не освободится узел для запомненного элемента. После этого поместить запомненный элемент на освободившееся место. Более точно это можно выразить с помощью следующих операторов:
Операция ПОГРУЖЕНИЕ. Эта операция также применяется для восстановления свойства кучеобразности. Пусть, например, в -м узле расположен элемент , нарушающий кучеобразный порядок таким образом, что ключ элемента больше ключа элемента , приписанного потомку узла . В этом случае среди непосредственных потомков узла выбирается элемент с наименьшим ключом, и элементы и меняются местами. Если после этого элемент снова не удовлетворяет условиям кучи, то еще раз проводим аналогичную перестановку. И так до тех пор, пока не встанет на свое место.
Рассмотрим -дерево, представленное на рис. 4.6. В узле расположен элемент с ключом , и этот узел имеет двух потомков с меньшими ключами, а именно и . Применим к элементу
операцию ПОГРУЖЕНИЕ.
Рис. 4.6.
Среди непосредственных потомков узла 1 находим узел, которому приписан элемент с наименьшим ключом, в нашем случае это узел c ключом . Меняем местами элементы
и . В результате получается дерево, изображенное на рис. 4.7.
Рис. 4.7.
Теперь элемент снова имеет потомка с меньшим, чем у него, ключом (а точнее, оба его потомка имеют меньшие ключи). Снова находим непосредственного потомка элемента с наименьшим ключом, и меняем его и местами. Получается дерево, изображенное на рис. 4.8.
Рис. 4.8.
Теперь находится в узле 17 и не имеет потомков с меньшим, чем у него, ключом (точнее, у него вообще нет потомков). Операция ПОГРУЖЕНИЕ завершена.
Вычислительная сложность этой операции пропорциональна числу сравнений элементов и их обменов. Для каждого узла в пути следования данной операции производится сравнений (при поиске потомка с минимальным ключом) и один обмен. Длина этого пути в -куче с узлами не превосходит ее высоты, а именно , по доказанному выше утверждению 1. Значит, время выполнения данной операции — .
Для реализации операции погружения воспользуемся функцией\linebreak , позволяющей для любого узла находить его непосредственного потомка с минимальным ключом.
