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

Проблема заключается в следующем: рассмотренная нами реализация сортирующего дерева в виде массива требует, чтобы отсчет элементов массива начинался единицы, а не с нуля, как имеет место в структуре 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}

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;

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

{Примечание: дочерние узлы родительского узла n располагаются в позициях 2n+1 и 2n+2}

ChildInx := (FromInx * 2) + 1;

{если существует по меньшей мере левый дочерний узел...}

while (ChildInx <= MaxInx) do

begin

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

if (succ(ChildInx) <= MaxInx) and

(FCompare(FList.List^[ChildInx], FList.List^[succ(ChildInx) ]) < 0) then

inc(ChildInx);

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

if (FCompare(Item, FList.List^[ChildInx]) >= 0) then

Break;

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

FList.List^[FromInx] := FList.List^[ChildInx];

FromInx := ChildInx;

ChildInx := (FromInx * 2) + 1;

end;

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

FList.List^[FromInx] := Item;

end;

function TtdPriorityQueue.Dequeue : pointer;

begin

{проверить наличие элемента для его исключения из очереди}

if (FList.Count = 0) then

pqError(tdeQueueIsEmpty, 'Dequeue');

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

Result := FList.List^[0];

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

if (FList.Count = 1) then

FList.Count := 0

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

else

if (FList.Count = 2) then begin

FList.List^[0] := FList.List^[1];

FList.Count := 1;

end

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

else begin

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

FList.List^[0] := FList.Last;

FList.Count := FList.Count - 1;

pqTrickleDownStd;

end;

end;

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

Роберт Флойд (Robert Floyd) обратил внимание, что первый шаг операции исключения из очереди требует удаления элемента с наивысшим приоритетом и замены его одним из наименьших элементов сортирующего дерева. Этот элемент не обязательно должен быть наименьшим, но в процессе применения алгоритма просачивания он наверняка будет перемещен на один из нижних уровней дерева. Иначе говоря, большинство операций сравнения родительского элемента с его большим дочерним элементом, выполняемое в ходе процесса просачивания, вероятно, лишено особого смысла, поскольку результат сравнения заведомо известен: родительский элемент будет меньше своего большего дочернего элемента. Поэтом