FList := TList.Create;
end;
destructor TtdPriorityQueue.Destroy;
begin
Clear;
FList.Free;
inherited Destroy;
end;
Код реализации алгоритма вставки и процедуры, выполняющей реальную операцию пузырькового подъема, показан в листинге 9.5. Операция вставки реализована так, чтобы гарантировать размещение наибольшего элемента в корневом узле. Этот тип очереди по приоритету обычно называют пирамидальной сортировкой выбором максимального элемента (max-heap). Если изменить процедуру сравнения так, чтобы она возвращала отрицательное число, если первый элемент больше второго, в корневом узле очереди по приоритету будет располагаться наименьший элемент. Такая сортировка называется пирамидальной сортировкой выбором наименьшего элемента (min-heap).
Листинг 9.5. Вставка в TtdPriorityQueue: постановка в очередь
procedure TtdPriorityQueue.pqBubbleUp(aFromInx : integer);
var
ParentInx : integer;
Item : pointer;
begin
Item := FList.List^ [aFromInx];
{если анализируемый элемент больше своего родительского элемента, необходимо поменять его местами с родительским элементом и продолжить процесс из новой позиции элемента}
{Примечание: родительский узел узла, имеющего индекс n, располагается в позиции (n-1)/2}
ParentInx := (aFromInx - 1) div 2;
{если данный элемент имеет родительский узел и больше родительского элемента...}
while (aFromInx > 0) and (FCompare(Item, FList.List^[ParentInx]) > 0) do
begin
{необходимо переместить родительский элемент вниз по дереву}
FList.List^[aFromInx] := FList.List^[ParentInx];
aFromInx := ParentInx;
ParentInx := (aFromInx - 1) div 2;
end;
{сохранить элемент в правильной позиции}
FList.List^[aFromInx] := Item;
end;
procedure TtdPriorityQueue.Enqueue(aItem : pointer);
begin
{добавить элемент в конец списка и выполнить его пузырьковый подъем на максимально возможный уровень}
FList.Add(aItem);
pqBubbleup(pred(FList.Count));
end;
В листинге 9.6 приведен фрагмент кода, реализующий последнюю часть очереди по приоритету: алгоритм удаления и процедуру, которая выполняет операцию просачивания вниз.
Листинг 9.6. Удаление из TtdPriorityQueue: исключение из очереди
procedure TtdPriorityQueue.pqTrickleDownStd;
var
FromInx : integer;
ChildInx : integer;
MaxInx : integer;
Item : pointer;
begin
FromInx := 0;
Item := FList.List^[0];
MaxInx := FList.Count - 1;
{если анализируемый элемент меньше одного из его дочерних элементов, нужно поменять его местами с большим дочерним элементом и продолжить процесс из новой позиции}