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

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

Этот процесс нужно продолжать до тех пор, пока элементы в сортирующем дереве не иссякнут. В результате мы получаем элементы исходного массива, но теперь они оказываются отсортированными.

Полный код подпрограммы пирамидальной сортировки, реализованной так же, как были реализованы все процедуры сортировки в главе 5, приведен листинге 9.8.

Листинг 9.8. Алгоритм пирамидальной сортировки

procedure HSTrickleDown( aList : PPointerList; aFromInx : integer;

aCount : integer; aCompare : TtdCompareFunc );

var

Item : pointer;

ChildInx : integer;

ParentInx: integer;

begin

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

Item := aList^[aFromInx];

ChildInx := (aFromInx * 2) + 1;

while (ChildInx < aCount) do

begin

if (suce(ChildInx) < aCount) and

(aCompare(aList^[ChildInx], aList^[suce(ChildInx)]) < 0) then

inc(ChildInx);

aList^[aFromInx] := aList^[ChildInx];

aFromInx := ChildInx;

ChildInx := (aFromInx * 2) + 1;

end;

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

ParentInx := (aFromInx - 1) div 2;

while (aFromInx > 0) and (aCompare (Item, aList^[ParentInx] ) > 0) do

begin

aList^[aFromInx] := aList^[ParentInx];

aFromInx := ParentInx;

ParentInx := (aFromInx - 1) div 2;

end;

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

aList^[aFromInx] := Item;

end;

procedure HSTrickleDownStd( aList : PPointerList;

aFromInx : integer;

aCount : integer;

aCompare : TtdCompareFunc );

var

Item : pointer;

ChildInx : integer;

begin

Item := aList^[aFromInx];

ChildInx := (aFromInx * 2) + 1;

while (ChildInx < aCount) do

begin

if (succ(ChildInx) < aCount) and

(aCompare(aList^[ChildInx], aList^[succ(ChildInx)]) < 0) then

inc(ChildInx);

if aCompare(Item, aList^[ChildInx]) >= 0 then

Break;

aList^[aFromInx] := aList^[ChildInx];

aFromInx := ChildInx;

ChildInx := (aFromInx * 2) + 1;

end;

aList^[aFromInx] := Item;

end;

procedure TDHeapSort( aList : TList; aFirst : integer;

aLast : integer; aCompare : TtdCompareFunc );

var

ItemCount : integer;

Inx : integer;

Temp : pointer;

begin

TDValidateListRange(aList, aFirst, aLast, 'TDHeapSort');

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

ItemCount := aLast - aFirst + 1;

for Inx := pred( ItemCount div 2) downto 0 do

HSTrickleDownStd(@aList.List^[aFirst], Inx, ItemCount, aCompare);

{удаление элементов из сортирующего дерева по одному, с помещением их в конец массива}

for Inx := pred( ItemCount) downto 0 do

begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[aFirst+Inx];

aList.List^ [aFirst+Inx] :=Temp;

HSTrickleDown(@aList.List^[aFirst], 0, Inx, aCompare);

end;

end;

Обратите внимание, что на первом этапе, при создании сортирующего дерева из массива, мы использовали стандартный алгоритм просачивания (алгоритм Флойда), но на втором этапе (при удалении наибольшего элемента из постоянно уменьшающегося сортирующего дерева) был применен оптимизированный алгоритм просачивания Флойда. На первом этапе мы ничего не знали о распределении элементов в массиве, поэтому имело смысл просто применить стандартный алгоритм просачивания - в конце концов, в целом алгоритм Флойда является операцией типа O(n). Однако на втором этапе мы знаем, что меняем местами наибольший элемент и один из наименьших элементов. Поэтому в целесообразно осуществить оптимизацию.

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