Описание алгоритма
Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n-1 элементов и т. д. Сумма первых n-1 целых равна
Второй этап сортировки – спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путём замены либо на пустой элемент(дырку) в самом низу, либо на элемент из соседней ветви в промежуточных вершинах. Элемент, передвинувшийся в корень дерева, вновь будет наименьшим(теперь уже вторым) ключом, и его можно исключить. После n таких шагов дерево станет пустым (то есть в нём останутся только дырки), и процесс сортировки заканчивается. Обратим внимание – на каждом из n шагов выбора требуется только log2 n cравнений. Поэтому на весь процесс понадобится порядка n log2 n элементарных операций плюс ещё n шагов на построение дерева. Это весьма существенное улучшение не только прямого метода, требующего n2 шагов, но и даже метода Шелла, где нужно n1,2 шага. Естественно, сохранение дополнительной информации делает задачу более изощрённой, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Ведь в конце концов для сохранения избыточной информации, получаемой при начальном проходе, создаётся некоторая древообразная структура. Наша следующая задача – найти приёмы эффективной организации этой информации.
Конечно, хотелось бы, в частности, избавиться от дырок, которыми в конечном итоге будет заполнено всё дерево и которые порождают много ненужных сравнений. Кроме того, надо было бы поискать такое представление дерева из n элементов, которое требует лишь n единиц памяти, а не 2n-1, как это было раньше.
Этих целей действительно удалось добиться в рассматриваемом методе 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
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;
