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


         

Теперь пирамида расширяется влево; каждый


      j := j + 1;
  end;
end; 
Теперь пирамида расширяется влево; каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Следовательно, процесс формирования пирамиды из n элементов h[1]...h[n] на том же самом месте описывается так:
L := (n div 2) + 1;
while L > 1 do
begin
  L := L - 1;
  sift(L, n);
end;
Для того, чтобы получиь не только частичную, но и полную упорядоченность среди элементов, нужно проделать n сдвигающих шагов, причём после каждого шага на вершину дерева выталкивается очередной(наименьший) элемент. И вновь возникает вопрос: где хранить "всплывающие" верхние элементы и можно ли или нельзя проводить обращение на том же месте? Существует, конечно, такой выход: каждый раз брать последнюю компоненту пирамиды (скажем, это будет х), прятать верхний элемент в освободившемся теперь месте, а х сдвигать в нужное место.  Процесс описывается с помощью процедуры sift таким образом:
R := n;
while R > 1 do
begin
  Swap(a[1], a[R]);
  R := R - 1;
  sift(1, R);
end;
Однако получившийся порядок фактически является обратным. Это можно легко исправить, изменив направление "упорядочивающего отношения" в процедуре sift. В конце концов получаем процедуру HeapSort
Листинг 2. HeapSort
procedure HeapSort;
var
  L, R : index;
  x : item;
procedure Swap(var a, b : item);
{ меняет значения переменных}
var c : item;
begin
  c := a;
  a := b;
  b := c;
end;
 
procedure sift(L, R : index);
var
  i, j : index;
  x : item;
begin
    i := j; 
    j := 2 * j;
    if (j < R) and (a[j+1] > a[j]) then
      j := j + 1;
  end;
end; 
begin
  L := (n div 2) + 1;
  R := n;
  while (L > 1) do
  begin
    L := L - 1;
    sift(L, R);
  end;
  while R > 1 do
  begin
    Swap(a[1], a[R]);
    R := R - 1;
    sift(L, R);
  end;
end;

Содержание  Назад  Вперед