333
правки
Изменения
→merge
=== merge ===
Эта операция, соединяющая две биномиальные кучи в одну, часто используется в качестве подпрограммы большинством остальных при реализации других операций.
Для этого нам надо сначала слить списки корней <tex>H_1, H_2</tex> в единый связный список, отсортированный по степеням в монотонно возрастающем порядке. Для каждого элемента списка известна ссылка на следующего и предыдущего корня. Свойство пирамиды обеспечивает нам в новом списке наличие не более двух деревьев одинаковой степени. Далее мы за один проход по этому списку объединим некоторые деревья так, что в результате все они будут иметь попарно разные степени. Рассмотрим подробнее процесс прохождения по этому списку:
