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