1.7 Алгоритм пирамиды (метод Уильямса-Флойда)
Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма "пирамиды". Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого "пирамидой". Алгоритм имеет гарантированную трудоемкость вида 0(n log n) и не требует дополнительной памяти.
Высокая эффективность алгоритма и гарантированная надежность для самого "худшего" случая часто оказываются решающими факторами, заставляющими отдавать предпочтение этому способу сортировки.
Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду "пирамиды".
На втором этапе осуществляется сортировка "пирамиды".
Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:
А[1]
А[2] А[3]
А[4] А[5] А[6] А[7]
А[8] А[9]...
Структура дерева имеет логический характер - в памяти компьютера все элементы массива все равно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка A[2i] и A[2i+1], где i - индекс данного элемента ("предка"). Элементы массива, являющегося "пирамидой", обладают следующими дополнительными свойствами:
1. Любой элемент пирамиды A[i] не меньше, чем его элементы-потомки A[2i] и A[2i+1] (соответственно первый элемент обладает максимальным значением):
A[i]>=A[2i],
A[i] >= A[2i+1]
2. Любая подпоследовательность элементов вида А[n\2+1], А[n\2+2], ... А[n] также является пирамидой, обладающей свойствами 1 и 2.
После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.
В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и "укоротим" массив на 1 элемент с "хвоста". Наибольший элемент массива окажется последним.
"Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент А[1] и его потомки - А[2| и А[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент А[1] и наибольший из потомков: mах( А[2], А[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом.
{ Метод "пирамиды" (алгоритм Вильямса-Флойда) }
procedure PIR;
var t, k, i: integer;
begin
for i : = 2 to n do { создание структуры бинарного дерева-"пирамиды" }
begin
t:=i;
while t <>1 do
begin
k := t div 2;
if a[k] >= a[t] then
t := 1
else
begin
OBMEN(a[k],a[t]);t :=k
end
end
end;
for i :=n-l downto 1 do { сортировка массива-"пирамиды"}
begin
OBMEN(a[i+l],a[l]);t:=l;
while t <> 0 do
begin
k := t+1;
if k>I then
t:=0
else
begin
if k < i then if a[k+l] > a[k] then
k : = k+1;
if a[t]>=a[k] then
t:=0
else
begin
OBMEN(a[t],a[k]);t:=k
end
end
end
end
end;