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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 5.8. 

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

Рис. 5.9. 

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

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

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

Рис. 5.10. 

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