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




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



Рис. 5.15. 

Ключ узла уменьшается до 0, куча при этом все еще остается левосторонней (рис. 5.16).


Рис. 5.16. 

Следуем от узла до корня дерева , для каждого узла этого пути восстанавливаем свойство левизны и ранг. Сначала проверяем узел : его детей надо поменять местами (а фактически — только одного-единственного правого сына сделать левым). После этого вычисляется новый ранг узла : он равен рангу правого сына плюс 1, то есть 1 (так как правого сына нет). Получилось дерево, изображенное на рис. 5.17.


Рис. 5.17. 

Следующий узел — это родитель узла

с ключом . Его потомков тоже необходимо поменять местами (так как ранг левого сына меньше ранга правого). После этого ранг узла с ключом вычисляется как ранг правого сына плюс , то есть . Получается куча, представленная на рис. 5.18.


Рис. 5.18. 

Наконец, сливаем кучи и , получая в результате левостороннюю кучу (рис. 5.19).


Рис. 5.19. 

Реализация операции УМЕНЬШИТЬ_КЛЮЧ

Операция ОБРАЗОВАТЬ_ОЧЕРЕДЬ. Из элементов списка образуется левосторонняя куча . Способ формирования такой кучи посредством применений операции ВСТАВИТЬ неэффективен. Читателю предоставляется возможность доказать, что в худшем случае формирование кучи таким способом может потребовать операций, где .

Более эффективным является следующий способ образования -элементной левосторонней кучи. Заводится список , в который помещаются

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

Читателю предоставляется возможность доказать, что время выполнения операции ОБРАЗОВАТЬ_ОЧЕРЕДЬ таким способом — .

Реализация операции ОБРАЗОВАТЬ_ОЧЕРЕДЬ




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