Реализация операции УДАЛЕНИЕ_МИНИНИМУМА
Операция МИНИМУМ. Эта операция позволяет взять из кучи элемент с минимальным ключом, не удаляя его из кучи. Поскольку элемент с минимальным ключом находится в корне кучи, требуется лишь скопировать его в нужное место. Вычислительная сложность данной операции .
Реализация операции МИНИМУМ
Операция УДАЛЕНИЕ. Эта операция позволяет удалить из кучи
элемент , расположенный в узле, заданном позицией . Удаление может быть проведено в несколько этапов.
с корнем в удаляемом узле . Оставшаяся куча, для которой сохраняем обозначение , не обязательно является левосторонней.
(время выполнения — , как доказано выше).
( — родитель узла ), каким являлся для нее узел
(левым или правым).
узлов на этом пути (потому что максимальный по длине правый путь имеет максимум узлов).
Таким образом, время выполнения операции — .
Рассмотрим пример выполнения данной операции. Пусть из кучи , изображенной на рис. 5.8, необходимо удалить элемент с ключом .
Рис. 5.8.
Сначала отрывается подкуча с корнем . От остаются куча (нелевосторонняя, так как свойству левизны не удовлетворяет узел ) и левосторонняя куча (рис. 5.9).
Рис. 5.9.
Затем удаляется узел , а его левая и правая подкучи
и сливаются в одну кучу
при помощи описанной выше операции СЛИЯНИЕ; см. рис. 5.10.
Рис. 5.10.
Поскольку узел не являлся корнем кучи , операция еще не завершена. Куча становится левым поддеревом узла , так как узел был его левым сыном (рис. 5.11).