Структуры данных и модели вычислений



         

Операции с d-кучей - часть 2


в узел , затем из узла в узел

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

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

Рассмотрим -дерево, представленное на рис. 4.6. В узле расположен элемент с ключом , и этот узел имеет двух потомков с меньшими ключами, а именно и . Применим к элементу

операцию ПОГРУЖЕНИЕ.


Рис. 4.6. 




Содержание  Назад  Вперед