Структуры данных и модели вычислений
Ключ узла уменьшается до 0,
Рис. 5.15.
Ключ узла уменьшается до 0, куча при этом все еще остается левосторонней (рис. 5.16).
Рис. 5.16.
Следуем от узла до корня дерева , для каждого узла этого пути восстанавливаем свойство левизны и ранг. Сначала проверяем узел : его детей надо поменять местами (а фактически — только одного-единственного правого сына сделать левым). После этого вычисляется новый ранг узла : он равен рангу правого сына плюс 1, то есть 1 (так как правого сына нет). Получилось дерево, изображенное на рис. 5.17.
Рис. 5.17.
Следующий узел — это родитель узла
с ключом . Его потомков тоже необходимо поменять местами (так как ранг левого сына меньше ранга правого). После этого ранг узла с ключом вычисляется как ранг правого сына плюс , то есть . Получается куча, представленная на рис. 5.18.
Рис. 5.18.
Наконец, сливаем кучи и , получая в результате левостороннюю кучу (рис. 5.19).
Рис. 5.19.
Реализация операции УМЕНЬШИТЬ_КЛЮЧ
Операция ОБРАЗОВАТЬ_ОЧЕРЕДЬ. Из элементов списка образуется левосторонняя куча . Способ формирования такой кучи посредством применений операции ВСТАВИТЬ неэффективен. Читателю предоставляется возможность доказать, что в худшем случае формирование кучи таким способом может потребовать операций, где .
Более эффективным является следующий способ образования -элементной левосторонней кучи. Заводится список , в который помещаются
одноэлементных куч. Пока длина списка больше 1, из его начала извлекаются две кучи, производится их слияние, а полученная куча вставляется в конец списка .
Читателю предоставляется возможность доказать, что время выполнения операции ОБРАЗОВАТЬ_ОЧЕРЕДЬ таким способом — .
Реализация операции ОБРАЗОВАТЬ_ОЧЕРЕДЬ
