With h^ Do Begin

parent:= nil;

child:= nil;

sibl:= nil;

degree:=0;

key:=x;

End;

Merge(h,head,head);{Сливаем кучи: кучу из одного элемента и старую кучу.}

End;

С операцией Extract _ min дела обстоят чуть сложнее (рис. 7.19). Так как минимальный элемент в каждом биномиальном дереве кучи находится в корне, то необходимо просмотреть корневой список. Пусть дана куча из B ₂, B ₄, B ₅, B ₇ и минимальный элемент находится в B ₅ (рис. 7.19, система обозначений та же, что и на предыдущих рисунках). Куча распадается на две. В первой те биномиальные деревья, которые были в исходной куче до дерева с минимальным элементом, а во второй – поддеревья с корнями, являющимися сыновьями удаленного корня дерева, и элементы кучи, которые следовали в исходной после удаленного дерева (можно сделать и иначе – «остаток» в первую кучу). На рис. 7.19 приведена структура (для примера) первой и второй куч. Дальнейшее очевидно – выполняем операцию Merge для полученных куч.

Рис. 7.19. Иллюстрация операции Extract_Min

Function Extract_Min(Var head:pt): Integer;

Var x: Integer;

h,prev,p,next:pt;

Begin

x:= maxint; {Имитация бесконечного значения.}

If (head<> nil) Then Begin {Ищем элемент с минимальным ключом.}

p:=head;

prev:= nil;

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