узел и самый нижний крайний справа узел, уменьшить значение счетчика количества элементов сортирующего дерева, а затем применить алгоритм просачивания.
Этот процесс нужно продолжать до тех пор, пока элементы в сортирующем дереве не иссякнут. В результате мы получаем элементы исходного массива, но теперь они оказываются отсортированными.
Полный код подпрограммы пирамидальной сортировки, реализованной так же, как были реализованы все процедуры сортировки в главе 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). Однако на втором этапе мы знаем, что меняем местами наибольший элемент и один из наименьших элементов. Поэтому в целесообразно осуществить оптимизацию.
До сих пор не был пояснен один момент. Если в качестве очереди по приоритету используется сортирующее дерево, отсортированное выбором максимального элемента, извлечение элементов будет выполняться в обратном порядке - начиная с наибольшего и заканчивая наименьшим. Однако если
