Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

FromInx := Handle^.peInx;

if (FromInx > 0) then begin

ParentInx := (FromInx - 1) div 2;

ParentHandle := PpqexNode(FList.List^[ParentInx]);

{если элемент имеет родительский элемент и больше нее о...}

while (FromInx > 0) and

(FCompare (Handle^.peItem, ParentHandle^.peItem) > 0) do

begin

{нужно переместить родительский элемент вниз по дереву}

FList.List^[FromInx] := ParentHandle;

ParentHandle^.peInx := FromInx;

FromInx := ParentInx;

ParentInx := (FromInx - 1) div 2;

ParentHandle := PpqexNode(FList.List^[ParentInx]);

end;

end;

{сохранить

элемент в правильной позиции}

FList.List^[FromInx] := Handle;

Handle^.peInx := FromInx;

end;

function TtdPriorityQueueEx.Enqueue(aItem : pointer): TtdPQHandle;

var

Handle : PpqexNode;

begin

{создать новый узел для связного списка}

Handle := AddLinkedListNode(FHandles, aItem);

{добавить дескриптор в конец очереди}

FList.Add(Handle);

Handle^.peInx := pred(FList.Count);

{теперь нужно выполнить его пузырьковый подъемна максимально возможный уровень}

if (FList.Count > 1) then

pqBubbleUp(Handle);

{вернуть дескриптор}

Result := Handle;

end;

Подобно методу Enqueue, все эти косвенные ссылки несколько усложняют метод Dequeue, но в коде все же можно распознать стандартные операции исключения из очереди и просачивания.

Листинг 9.11. Исключение из очереди и просачивание в расширенной очереди по приоритету

procedure TtdPriorityQueueEx.pqTrickleDown(aHandle : TtdPQHandle);

var

FromInx : integer;

MaxInx : integer;

ChildInx : integer;

ChildHandle : PpqexNode;

Handle : PpqexNode absolute aHandle;

begin

{если анализируемый элемент меньше одного из своих дочерних элементов, его нужно поменять местами с большим дочерним элементом и продолжить процесс из новой позиции}

FromInx := Handle^.peInx;

MaxInx := pred(FList.Count);

{вычислить индекс левого дочернего узла}

ChildInx := succ(FromInx * 2);

{если имеется по меньшей мере правый дочерний элемент, необходимо вычислить индекс большего дочернего элемента...}

while (ChildInx <= MaxInx) do

begin

{если есть хоть один правый дочерний узел, вычислить индекс наибольшего дочернего узла}

if ((ChildInx+1) <= MaxInx) and

(FCompare(PpqexNode(FList.List^[ChildInx])^.peItem, PpqexNode(FList.List^[ChildInx+ 1])^.peItem) < 0) then

inc(ChildInx);

{если элемент больше или равен большему дочернему элементу, задача выполнена}

ChildHandle := PpqexNode(FList.List^[ChildInx]);

if (FCompare (Handle^.peItem, ChildHandle^.peItem) >= 0) then

Break;

{в

противном случае больший дочерний элемент нужно переместить вверх по дереву, а сам элемент - вниз}

FList.List^[FromInx] ChildHandle;

ChildHandle^.peInx := FromInx;

FromInx := ChildInx;

ChildInx := succ(FromInx * 2);

end;

{сохранить элемент в правильной позиции}

FList.List^[FromInx] := Handle;

Handle^.peInx := FromInx;

end;

function TtdPriorityQueueEx.Dequeue : pointer;

var

Handle : PpqexNode;

begin

{проверить наличие элементов, которые нужно исключить из очереди}

if (FList.Count = 0) then

pqError(tdeQueueIsEmpty, 'Dequeue');

{вернуть корневой элемент, удалить его из списка дескрипторов}

Handle := FList.List^[0];

Result := Handle^.peItem;

DeleteLinkedListNode(FHandles, Handle);

{если очередь содержала только один элемент, теперь она пуста}

if (FList.Count = 1) then

FList.Count := 0

{если она содержала два элемента, нужно просто заменить корневой элемент одним из оставшихся дочерних элементов. Очевидно, что при этом свойство пирамидальности сохраняется}

else

if (FList.Count = 2) then begin

Handle := FList.List^[1];

FList.List^[0] := Handle;

FList.Count := 1;

Handle^.peInx := 0;

end

{в противном случае свойство пирамидальности требует восстановления}

else begin

{заменить корневой узел дочерним узлом, расположенным в самой нижней, крайней справа позиции, и уменьшить размер списка; затем за счет применения метода просачивания переместить корневой узел как можно дальше вниз по дереву}

Handle := FList.Last;

FList.List^[0] := Handler-Handle^.peInx := 0;

FList.Count := FList.Count - 1;

pqTrickleDown(Handle);

end;

end;

После ознакомления с операциями постановки в очередь и исключения из нее можно рассмотреть новые операции: удаление и изменение приоритета. Метод ChangePriotity крайне прост. Прежде чем метод будет вызван, класс предполагает, что приоритет элемента был изменен. Вначале метод проверяет, имеет ли элемент родительский элемент, и если да, то больше ли элемент с новым приоритетом своего родительского элемента. Если это так, то элемент перемещается вверх за счет применения метода пузырькового подъема. Если операция пузырькового подъема невозможна или не требуется, метод проверяет возможность выполнения операции просачивания.