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 крайне прост. Прежде чем метод будет вызван, класс предполагает, что приоритет элемента был изменен. Вначале метод проверяет, имеет ли элемент родительский элемент, и если да, то больше ли элемент с новым приоритетом своего родительского элемента. Если это так, то элемент перемещается вверх за счет применения метода пузырькового подъема. Если операция пузырькового подъема невозможна или не требуется, метод проверяет возможность выполнения операции просачивания.
Листинг 9.12. Восстановление свойства пирамидальности после изменения приоритета
procedure TtdPriorityQueueEx.ChangePriority(aHandle : TtdPQHandle);
var
Handle : PpqexNode absolute aHandle;
ParentInx : integer;
ParentHandle : PpqexNode;
begin
{проверить возможность выполнения операции пузырькового подъема}
if (Handle^.peInx > 0) then begin
ParentInx := (Handle^.peInx - 1) div 2;
ParentHandle := PpqexNode(FList[ParentInx]);
if (FCompare( Handle^.peItem, Parent Handle^.peItem) > 0) then begin
pqBubbleUp(Handle);
Exit;
end;
end;
{в противном случае выполнить операцию просачивания}
pqTrickleDown(Handle);
end;
Последняя операция реализуется при помощи метода Remove. В данном случае мы возвращаем элемент, определенный дескриптором, а затем заменяем его последним элементом сортирующего дерева. Дескриптор удаляется из связного списка. Эта операция упрощается благодаря использованию двусвязного списка. Затем значение счетчика элементов в сортирующем дереве уменьшается на единицу. С этого момента процесс полностью совпадает с процессом изменения приоритета, поэтому мы просто вызываем соответствующий метод.
Листинг 9.13. Удаление элемента, заданного его дескриптором
function TtdPriorityQueueEx.Remove(aHandle : TtdPQHandle): pointer;