На рисунке 20.5 показан пример объединения двух куч, в котором встречаются все четыре случая, предусмотренные в тексте процедуры.

Работа процедуры Binomial-Heap-Union начинается с соединения корневых списков куч Н\ и Н2 в единый список Н, в котором корневые вершины идут в порядке возрастания их степеней (вызов Binomial-Heap-Merge).

В получившемся списке может быть до двух вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени с помощью процедуры Binomial-Link и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению столбиком, и время его работы пропорционально числу корневых вершин.

Опишем работу процедуры более подробно. Сначала (строки 13) происходит слияние корневых списков биномиальных куч Н\ и Н2 в один корневой список Н. Процедура Binomial-Heap-Merge на каждом шаге своей работы сравнивает начала списков Н\ и Н2 и вершину с меньшей степенью добавляет в конец списка Н. При этом порядок сохраняется, так что в списке Н степени корневых вершин идут в неубывающем порядке. Процедура Binomial-Heap-Merge требует времени О (га), где га - суммарная длина списков Hi и Я2.

Если кучи Н\ и Н2 пусты, будет возвращена пустая куча (строки 4-5). Далее мы предполагаем, что список Н содержит хотя бы одну вершину.

В цикле используются три указателя:

•ж указывает на текущую корневую вершину;

•prev-x указывает на предшествующую вершину (sibling[prev-x\ =

• next-x указывает на вершину, следующую за ж в списке (sibling[x] = next-x).

Изначально в списке Н может быть не более двух вершин данной степени, так как каждая из биномиальных куч Н\ и Н2 содержит не более одной вершины данной степени. Поскольку степени не убывают, вершины одинаковой степени будут соседними.

При сложении двоичных чисел столбиком в одном разряде может быть три единицы (две в слагаемых и одна за счёт переноса). По аналогичным причинам в ходе выполнения процедуры Binomial-Heap-Union в списке Н могут оказаться три вершины одинаковой степени.

Поэтому, видя в строке 10 две соседние вершины одинаковой степени, мы проверяем, не идёт ли за ними ещё одна вершина той же степени.

Заметим, что в начале каждой итерации цикла while (строки 921) ни один из указателей ж и next-x не равен nil.

Рис. 20.5 Исполнение процедуры BlNOMIAL-HEAP-union. (а) Биномиальные кучи Н\ и Н2. (б) Куча Н, возникающая после выполнения BINOMIAL-Неар-Merge( i, Н2); в переменной х находится первый корень из списка. Обе вершины х и next-x имеют степень 0, причем key[x] < key[next-x] (случай 3). (в) После связывания вершин (BINOMIAL-Link) х становится первым из трёх корней одинаковой степени (случай 2) (г) Указатели продвинуты вперёд на одну позицию вдоль корневого списка, х является первым из двух корней одинаковой степени (случай 4). (д) После связывания вершин возникает случай 3. (е) Ещё одно связывание приводит к случаю 1 (степень вершины х равна 3, а степень next-x равна 4). Продвижение указателей приведет к выходу из цикла, так как next-x станет равным NIL.

Случай 1, изображенный на рисунке 20.6а, возникает, когда degree[x] ф degree[next-x], т.е. когда х является корнем дерева Bk, а next-x - корнем дерева В\ для некоторого / > к. Данному случаю соответствуют строки 11-12. В этом случае мы просто продвигаем указатели на одну позицию (обновление указателя next-x будет выполнено в строке 21).

Случай 2, изображенный на рисунке 20.66, возникает, когда вершина х является первой среди трёх корневых вершин одинаковой степени (degree[x] = degree[next-x] = degree[sibling[next-x]]). И в этом случае мы продвигаем указатели вдоль списка.

В строке 10 мы проверяем, имеет ли место один из случаев 1 или 2, и в строках 11-12 выполняем продвижение указателей.

В случаях 3 и 4 за вершиной х следует ровно одна вершина той же степени: degree[x] = degree[next-x] ф degree[sibling[next-x]]. Это может произойти после обработки любого из случаев 1-4, но после случая 2 произойдёт наверняка. Мы связываем вершины х и next-x; какая из них остаётся корнем, зависит от того, как соотносятся ключи в этих двух вершинах.

В случае 3 (рис. 20.6в) кеу[х] key[next-x], поэтому вершина next-x подвешивается к вершине х. Строка 14 удаляет вершину