Изменения

Для этого нам надо сначала слить списки корней <tex>H_1, H_2</tex> в единый связный список, отсортированный по степеням в монотонно возрастающем порядке. Для каждого элемента списка известна ссылка на следующего и предыдущего корня. Свойство пирамиды обеспечивает нам в новом списке наличие не более двух деревьев одинаковой степени. Далее мы за один проход по этому списку объединим некоторые деревья так, что в результате все они будут иметь попарно разные степени. На Рассмотрим подробнее процесс прохождения по этому списку: Если текущий корень имеет разные степени с следующим за ним, то ничего с ним не делаем и продолжаем цикл. Это дерево в итоге останется в таком виде в конечной куче(случай <tex>a</tex> на рисунке). Если же степень текущего элемента равна степеням последующих двух вершин(это может случится в том случае, если в каждом из двух исходных деревьев был корень с этой степенью и еще одно дерево образовалось в ходе текущего слияния деревьев; причем более, чем трех корней с одинаковой степенью быть не может по нашему алгоритму и начальным условиям), то оставим это дерево нетронутым, но после на следующем шаге нам надо расмотреть несколько случаевсольем два других дерева с этой степенью. Иными словами переходим к следующей вершине, в которой уже будет происходить слияние(случай <tex>b</tex> на рисунке). В последнем случае мы имеем лишь две подряд вершины с одинаковой степенью корней. В этой ситуаций мы дерево с большим значением в корне вершины подвешиваем к дерево с меньшим значением в корне (случаи <tex> c, d</tex> на рисунке). Прим.на рисунке <tex>sibling[next-x]</tex> {{---}} следующий элемент в списке для <tex>next-x</tex>