Структуры данных и модели вычислений
и так до тех пор,
в узел , затем из узла в узел
и так до тех пор, пока не освободится узел для запомненного элемента. После этого поместить запомненный элемент на освободившееся место. Более точно это можно выразить с помощью следующих операторов:
Операция ПОГРУЖЕНИЕ. Эта операция также применяется для восстановления свойства кучеобразности. Пусть, например, в -м узле расположен элемент , нарушающий кучеобразный порядок таким образом, что ключ элемента больше ключа элемента , приписанного потомку узла . В этом случае среди непосредственных потомков узла выбирается элемент с наименьшим ключом, и элементы и меняются местами. Если после этого элемент снова не удовлетворяет условиям кучи, то еще раз проводим аналогичную перестановку. И так до тех пор, пока не встанет на свое место.
Рассмотрим -дерево, представленное на рис. 4.6. В узле расположен элемент с ключом , и этот узел имеет двух потомков с меньшими ключами, а именно и . Применим к элементу
операцию ПОГРУЖЕНИЕ.
Рис. 4.6.
