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


         

Этих целей действительно удалось добиться


Этих целей действительно удалось добиться в рассматриваемом методе Heapsort
(пирамидальная сортировка), изобретённом Д. Уилльямсом, где было получено, очевидно, существенное улучшение традиционных сортировок с помощью деревьев. Пирамида определяется как последовательность ключей h[L], h[L+1], ..., h[R], такая, что
h[i] <= h[2*i] and h[i] <= h[2*i+1] для i = L ... R/2.                             (1)
Если любое двоичное дерево рассматривать как массив, то можно говорить, что h[1] – наименьший элемент данного массива. Предположим, есть некоторая пирамида с заданными элементами h[L+1], ..., h[R] для некоторых значений L и R и нужно добавить новый элемент х, образуя расширенную пирамиду h[L], ..., h[R]. Новая пирамида получается так: сначала х ставится наверх древовидной структуры, а затем он постепенно опускается вниз каждый раз по направлению наименьшего из примыкающих к нему элементов, а сам этот элемент передвигается вверх. Как нетрудно заметить, данный способ не нарушает условий (1), определяющих пирамиду.
Р. Флойдом был предложен некий "лаконичный" способ построения пирамиды "на том же месте". Его процедура сдвига представлена как листинг 1. Здесь h[1]...h[n] ­­– некий массив, причём h[m]...h[n] (m = n div 2 + 1) уже образуют пирамиду, поскольку индексов i, j, удовлетворяющих соотношениям j = 2i и j = 2i+1 просто не существует. То есть эти элементы образуют нижний слой соответствующего двоичного дерева, для них никакой упорядоченности не требуется.
Листинг 1. Sift.
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 := L;
  j := 2*L;
  x := a[L];
  if (j < R) and (a[j+1] < a[j]) then
    j := j + 1;
  while (j <= R) and (a[j] < x) do
  begin
    Swap(a[i], a[j]);
    i := j; 
    j := 2 * j;
    if (j < R) and (a[j+1] < a[j]) then

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