Пирамидальная сортировка

Будем называть файл ключей К₁, К₂, …, К_N "пирамидой", если

К_[j/2] ³ К_j при 1 £ [j/2] < j £ N. (1)

В этом случае К₁ ³ К₂, К₁ ³ К₃, К₂ ³ К₄. и т.д. именно это условие выполняется на рис. Из этого следует, что К₁ = mах(К₁, К₂, …, К_N). (2)

Начальная задача состоит в том, чтобы произвольный последовательный файл преобразовать в пирамиду. Эффективный подход предложил Р.У.Флойд. Пусть нам удалось расположить файл таким образом, чтобы

К_[j/2] ³ К_j при l < [j/2] < j £ N, (3)

где l - некоторое число ³ 1. (В исходном файле (не упорядоченном) это условие "автоматически" выполняется только для l = [N / 2], поскольку ни один индекс j не удовлетворяет условию [N/2] £ [j/2] < j £ N.) Далее изменяя лишь поддерево с корнем в узле l, преобразовать файл, чтобы распространить неравенство (3) и на случай [j/2]= l. Следовательно, можно уменьшать l на 1, до тех пор, пока не будет достигнуто условие (1). Эти идеи Уильямса и Флойда приводят к изящному алгоритму.

Алгоритм У (пирамидальная сортировка).

Записи R₁, R₂, …, R_N переразмещаются на том же самом месте; после завершения сортировки их ключи будут упорядочены: К₁£ …£ К_N. Сначала файл перестраивается в пирамиду, после чего вершина пирамиды многократно исключается и записывается на свое окончательное место. Предполагается, что N ³ 2.

(Начальная установка) l:=[N/2]+1, r:=N.

(Уменьшить l или r) Если l > 1, то установить l:=l -1, R:=R _l , К:=К _j. (Если l >1, это означает, что происходит процесс преобразования исходного файла в пирамиду; если же l= 1, то это значит, что ключи К₁, К₂, …,К_r уже образуют пирамиду.) В противном случае установить R:=R_r, К:=К_r, R_r:=R₁ и r:=r-1; если в результате оказалось, что r=1, то установить R₁:=R и завершить работу алгоритма.

(Приготовиться к "протаскиванию") Установить j:= l. (К этому моменту К_[j/2] ³ К_j при l < [j/2] < j £ r (4), а записи R_k, r < k £ N, занимают свои окончательные места. Шаги У3–У8 называют алгоритмом "протаскивания"; их действие эквивалентно установке R _l = R с последующим перемещением записей R _l,…,R_r таким образом, чтобы условие (4) выполнилось и при [j/2] = l.)

(Продвинуться вниз) Установить i:=j и j:=2j (в последующих шагах i=[j/2].) Если j<r, то перейти к шагу У5; если j=r, то перейти к шагу У6; если же j>r, то перейти к шагу У8.

(Найти "большего" сына) Если К_j < К_j+1, то установить j:=j+1.

(Больше К?) Если К³К_j, то перейти к шагу У8.

(Поднять его вверх). Установить R_i:=R_j и возвратиться к шагу У4.

– алгоритм

(Занести R) Установить R_i:= R (На этом алгоритм "протаскивания", начатый на шаге У3, заканчивается). Возвратиться к шагу Н2.

Пирамидальную сортировку иногда описывают как это обозначение указывает на характер изменения переменных l и r. Верхний треугольник соответствует фазе построения пирамиды, когда r=N, а l убывает до 1. На Рис. 3 показан процесс пирамидальной сортироки для тех же 16 чисел.

Рис. 3 Процесс пирамидальной сортировки.

Листинг 8.10. Процедура pushdown

procedure pushdown (first, last: integer);

{ Элементы A[first],..., A[last] составляют частично

упорядоченное дерево за исключением, возможно, элемента A[first] и его сыновей. Процедура pushdown восстанавливает частично упорядоченное дерево }

Var

r: integer; { указывает текущую позицию А[first] }

Begin

r: = first; { инициализация }

while r <= last div 2 do

if last = 2*r then

Begin

{ элемент в позиции r имеет одного сына в позиции 2*r }

if A[r].key > A[2*r].key then swap(A(r], A[2*г]);

r:= last { досрочный выход из цикла while }

End

else { элемент в позиции r имеет двух сыновей в позициях 2*r и 2*r+1} if A[r] .key > A [2*r] .key and A[2*r] .key <= A[2*r + 1] .key then

begin { перестановка элемента в позиции r с левым сыном }

swap(A[r], A [2*r]);

r:= 2*r

End

else if A[r] .key > A [2*r + 1] .key and A[2*r + 1] .key < A[2*r].key then

begin { перестановка элемента в позиции г с правым сыном }

swap(A[r], A[2*r + 1]);

r:= 2*r + 1

End

Else

{элемент в позиции r не нарушает порядок в частично упорядоченном дереве }

r:= last { выход из цикла while }

end; { pushdown }

Вернемся к листингу 8.9 и займемся строками (4) - (6). Выбор минимального элемента в строке (4) прост — это всегда элемент А[1]. Чтобы исключить оператор печати в строке (5), мы поменяли местами элементы А[1] и A[i] в текущей куче. Удалить минимальный элемент из текущей кучи также легко: надо просто уменьшить на единицу курсор i, указывающий на конец текущей кучи. Затем надо вызвать процедуру pushdown(l, i - 1) для восстановления порядка в частично упорядоченном дереве кучи А[1],..., A[i - 1].

Вместо проверки в строке (3), не является ли множество S пустым, можно проверить значение курсора i, указывающего на конец текущей кучи. Теперь осталось рассмотреть способ выполнения операторов в строках (1), (2). Можно с самого начала поместить элементы списка L в массив А в произвольном порядке. Для создания первоначального частично упорядоченного дерева надо последовательно вызывать процедуру pushdown(j, п) для всех j = n/2, n/2 - 1,..., 1. Легко видеть, что после вызова процедуры pushdown(j, n) порядок в ранее упорядоченной части строящегося дерева не нарушается, так как новый элемент, добавляемый в дерево, не вносит нового нарушения порядка, поскольку он только меняется местами со своим "меньшим" сыном. Полный код процедуры heapsort (пирамидальная сортировка) показан в листинге 8.11.

Листинг 8.11. Процедура пирамидальной сортировки %

procedure heapsort;

{ Сортирует элементы массива А[1],..., А[n] в убывающем порядке }

Var

i: integer; { курсор в массиве А }

Begin

{ создание частично упорядоченного дерева }

(1) for i:= n div 2 downto 1 do

(2) pushdown (i, n);

(3) for i:= n downto 2 do

Begin

(4) swap(A[l], A[i]); { удаление минимального элемента из кучи }

(5) pushdown (1, i - 1)

{ восстановление частично упорядоченного дерева }

End

end; { heapsort }