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

         

Операции с левосторонними кучами - часть 3


Реализация операции УДАЛЕНИЕ_МИНИНИМУМА

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

Реализация операции МИНИМУМ

Операция УДАЛЕНИЕ. Эта операция позволяет удалить из кучи

элемент , расположенный в узле, заданном позицией . Удаление может быть проведено в несколько этапов.

  1. Если узел является корнем кучи , то применяется операция УДАЛЕНИЕ_МИНИМУМА из кучи . Иначе выполняются следующие действия.
  2. От исходной кучи отрывается подкуча

    с корнем в удаляемом узле . Оставшаяся куча, для которой сохраняем обозначение , не обязательно является левосторонней.

  3. Затем узел удаляется из кучи , а его левая и правая подкучи сливаются в одну кучу

    (время выполнения — , как доказано выше).

  4. Куча делается таким же сыном узла

    ( — родитель узла ), каким являлся для нее узел

    (левым или правым).

  5. Наконец, в куче восстанавливается свойство левизны. Фактически свойству левизны могут не удовлетворять только узлы, находящиеся на пути от к корню кучи . Длина этого пути в худшем случае может линейно зависеть от . Но на самом деле нам нужно проверить только первые не более чем

    узлов на этом пути (потому что максимальный по длине правый путь имеет максимум узлов).

Таким образом, время выполнения операции — .

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


Рис. 5.8. 

Сначала отрывается подкуча с корнем . От остаются куча (нелевосторонняя, так как свойству левизны не удовлетворяет узел ) и левосторонняя куча (рис. 5.9).


Рис. 5.9. 

Затем удаляется узел , а его левая и правая подкучи

и сливаются в одну кучу

при помощи описанной выше операции СЛИЯНИЕ; см. рис. 5.10.


Рис. 5.10. 

Поскольку узел не являлся корнем кучи , операция еще не завершена. Куча становится левым поддеревом узла , так как узел был его левым сыном (рис. 5.11).




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