Реализация очереди по приоритету при помощи сортирующего дерева
Код интерфейса результирующей очереди по приоритету, в которой используется сортирующее дерево и которая реализована при помощи структуры TList, приведен в листинге 9.3.
Листинг 9.3. Интерфейс класса TtdPriorityQueue
type
TtdPriorityQueue = class private
FCompare : TtdCompareFunc;
FDispose : TtdDisposeProc;
FList : TList;
FName : TtdNameString;
protected
function pqGetCount : integer;
procedure pqError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure pqBubbleUp(aFromInx : integer);
procedure pqTrickleDown;
procedure pqTrickleDownStd;
public
constructor Create(aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc );
destructor Destroy; override;
procedure Clear;
function Dequeue : pointer;
procedure Enqueue(aItem : pointer);
function Examine : pointer;
function IsEmpty : boolean;
property Count : integer read pqGetCount;
property Name : TtdNameString read FName write FName;
end;
Реализация и конструктора Create, и деструктора Destroy достаточно проста: первый должен создавать экземпляр TList, а второй должен всего лишь освобождать внутренний объект TList. Подобно стандартной очереди, конструктор Create нуждается в процедуре удаления элемента, позволяющей при необходимости освобождать элементы. Но, в отличие от стандартной очереди, теперь нам требуется процедура сравнения, позволяющая определить больший из двух элементов.
Листинг 9.4. Конструктор и деструктор очереди по приоритету
constructor TtdPriorityQueue.Create(aCompare : TtdCompareFunc;
aDispose : TtdDisposeProc);
begin
inherited Create;
if not Assigned(aCompare) then
pqError(tdePriQueueNoCompare, 'Create');
FCompare := aCompare;
FDispose :=aDispose;
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 приведен фрагмент кода, реализующий последнюю часть очереди по приоритету: алгоритм удаления и процедуру, которая выполняет операцию просачивания вниз.
