Рис. 20.7 Работа процедуры BlNOMIAL-HEAP-ExTRACT-MlN. (а) Исходная биномиальная куча Н. (б) Корневая вершина х, имеющая минимальный ключ, удалена из корневого списка Н. Она была корнем Вд-дерева, а её дети были корнями Bk - i-, Bk-2-, • • • , -Во-деревьев. (в) Обращая порядок, мы собираем потомков вершины х в биномиальную кучу Н. (г) Результат соединения куч Н и Я.

Рис. 20.8 Работа процедуры binomial-Heap-decrease-Key. (а) Перед началом цикла (ключ вершины у был уменьшен и стал меньше ключа родительской вершины z). (б) Перед второй итерацией цикла. Произошёл обмен ключами, указатели у и г продвинуты вверх, но свойство порядка пока нарушено, (в) После следующего обмена и сдвига указателей у и г вверх свойство упорядоченности выполнено, и цикл прекращается.

ная у содержит единственную вершину, в которой ключ может быть меньше ключей предков, аг - её родителя. Начинается цикл: если key[y] key[z] или если вершина у является корневой, то дерево упорядочено. В противном случае мы меняем местами содержимое вершин у и z, тем самым сдвигая место нарушения вверх по дереву, что отражено в строках 9-10.

Процедура Binomial-Heap-Decrease-Key выполняется за время О (lgra), поскольку глубина вершины х есть О (lgra) (утверждение 2 леммы 20.1), а при каждой итерации цикла while мы поднимаемся вверх.

Удаление вершины

Удаление вершины сводится к двум предыдущим операциям: мы уменьшаем ключ до -оо (специальное значение, про которое мы предполагаем, что оно меньше всех ключей), а затем удаляем вер-

шину с минимальным ключом.

В процессе выполнения процедуры Binomial-Heap-Decrease-Key специальное значение -оо (единственное в куче) всплывает вверх, откуда и удаляется процедурой Binomial-Heap-Extract-

MlN.

Binomial-Heap-Delete(#, ж)

1Binomial-Heap-Decrease-Key(#, ж, -оо)

2Binomial-Heap-Extract-Min(H)

(В упр. 20.2-6 предлагается переписать процедуру Binomial-Heap-Delete без использования дополнительного значения -оо.)

Процедура Binomial-Heap-Delete выполняется за время 0(lg га).

Упражнения

20.2-1 Объясните, почему слияние двоичных куч в смысле главы 7 требует времени О (га).

20.2-2 Напишите процедуру Binomial-Heap-Merge.

20.2-3 Нарисуйте биномиальную кучу, которая получается при добавлении вершины с ключом 24 к куче рис. 20.7г.

20.2-4 Нарисуйте биномиальную кучу, которая получается при удалении ключа 28 из кучи рис. 20.8в.

20.2-5 Почему процедура Binomial-Heap-Minimum не годится, если некоторые из ключей имеют значение оо? Как сделать её пригодной и для этого случая?

20.2-6 Не пользуясь специальным значением -оо, перепишите процедуру Binomial-Heap-Delete. (Оценка O(logra) для времени работы должна сохраниться.)

20.2-7 В чём состоит упоминавшаяся связь между соединением биномиальных куч и сложением двоичных чисел? Объясните связь между добавлением вершины в биномиальную кучу и прибавлением единицы к двоичному числу.

20.2-8 Имея в виду соответствие, упомянутое в упр. 20.2-7, перепишите процедуру Binomial-Heap-Insert так, чтобы она добавляла вершину в биномиальную кучу непосредственно, а не вызывала Binomial-Heap-Union.

20.2-9 Покажите, что если располагать вершины в корневых списках в порядке уменьшения (а не увеличения) степеней, то по-