If (x<>nil) And (y<>nil) Then Begin

If (x^.degree<y^.degree) Then Begin

z:=x;

Coufl(x^.sibl,y,z^.sibl);

End

Else Begin

z:=y;

Coufl(x,y^.sibl,z^.sibl);

End;

End

Else

If (x= nil) Then z:=y Else z:=x;

End;

Рис. 7.13. Пример слияния двух списков

Первая биномиальная куча на рис. 7.13 состоит из биномиальных деревьев B ₁, B ₂, B ₅ и B ₆, а вторая – из B ₀, B ₁, B ₂, B ₃ и B ₄.

Рис. 7.14. Сложение двух двоичных чисел 1100110 и 11111, соответствующих биномиальным кучам на рис. 7.13. В первой строке указаны степени двойки в разложении чисел, или порядки биномиальных деревьев

В результате сложения соответствующих двоичных чисел (рис. 7.14) получаем число 10000101. Другими словами в результате слияния куч – операция Merge – мы должны получить кучу, состоящую из биномиальных деревьев B ₀, B ₂, и B ₇ (рис. 7.15, в кружках по-прежнему указаны степени корней биномиальных деревьев).

Рис. 7.15. Результат слияния биномиальных куч, представленных на рис. 7.13

Рис. 7.16. Пример последовательного слияния двух биномиальных куч

Введем указатель x на текущую вершину корневого списка. В prev будет храниться адрес предыдущего элемента списка, а в next – следующего. В том случае, когда биномиальные деревья, соответствующие x и next, разного порядка, осуществляется простая переадресация по списку (случай 1 – рис. 7.17). Аналогичный переход осуществляется и тогда, когда x, next и next ^. sibl указывают на корневые вершины одинаковых биномиальных деревьев (случай 2 – рис. 7.17).

Рис. 7.17. Варианты простого перехода по корневому списку

Итак, слияние биномиальных деревьев выполняется (это явно просматривается на рис. 7.16) только в том случае, когда x и next соответствуют биномиальные деревья одного порядка, а next ^. sibl – более высокого порядка. Помня, что корневой список кучи должен содержать вершины, упорядоченные по неубыванию по параметру degree, следует проанализировать x ^. key и next ^. key. В зависимости от результата сравнения возможны два варианта – рис. 7.18.

Рис. 7.18. Варианты слияния биномиальных деревьев

Procedure Merge(head1,head2:pt; Var head:pt);

Var prev, x, next:pt;

Begin

Coufl(head1,head2,head); {Сливаем корневые списки.}

prev:= nil;

x:=head;

next:=x^.sibl;

Дата добавления: 2015-07-11