Теперь обратите внимание на нумерацию дочерних узлов каждого узла. Дочерними узлами корневого узла 1 являются, соответственно, узлы 2 и 3. Дочерними узлами узла 4 являются узлы 8 и 9, а узла 6 - узлы 12 и 13. Заметили ли вы какую-нибудь закономерность? Дочерними узлами узла n являются узлы 2n и 2n + 1, а родительским узлом узла n является узел nil. Теперь уже не обязательно, чтобы узел содержал указатели на родительский и дочерние узлы. Вместо этого можно воспользоваться простым арифметическим отношением. Таким образом, мы изобрели метод реализации сортирующего дерева при помощи массива, и решив более простую задачу, можно было бы снова отдать предпочтение структуре TList.

Проблема заключается в следующем: рассмотренная нами реализация сортирующего дерева в виде массива требует, чтобы отсчет элементов массива начинался единицы, а не с нуля, как имеет место в структуре TList. Этого достаточно легко добиться. Достаточно изменить арифметическую формулу вычисления индекса родительского и дочерних узлов. Дочерние узлы узла n должны располагаться в позициях In + 1 и In + 2, а родительский узел этого узла - в позиции (n -1)11.

Код интерфейса результирующей очереди по приоритету, в которой используется сортирующее дерево и которая реализована при помощи структуры 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}