Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Будем называть файл ключей К1, К2, …, КN "пирамидой", если
К[j/2] ³ Кj при 1 £ [j/2] < j £ N. (1)
В этом случае К1 ³ К2, К1 ³ К3, К2 ³ К4. и т.д. именно это условие выполняется на рис. Из этого следует, что К1 = mах(К1, К2, …, К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). Эти идеи Уильямса и Флойда приводят к изящному алгоритму.
Алгоритм У (пирамидальная сортировка).
Записи R1, R2, …, RN переразмещаются на том же самом месте; после завершения сортировки их ключи будут упорядочены: К1£ …£ КN. Сначала файл перестраивается в пирамиду, после чего вершина пирамиды многократно исключается и записывается на свое окончательное место. Предполагается, что N ³ 2.
(Начальная установка) l:=[N/2]+1, r:=N.
(Уменьшить l или r) Если l > 1, то установить l:=l -1, R:=R l , К:=К j. (Если l >1, это означает, что происходит процесс преобразования исходного файла в пирамиду; если же l= 1, то это значит, что ключи К1, К2, …,Кr уже образуют пирамиду.) В противном случае установить R:=Rr, К:=Кr, Rr:=R1 и r:=r-1; если в результате оказалось, что r=1, то установить R1:=R и завершить работу алгоритма.
(Приготовиться к "протаскиванию") Установить j:= l. (К этому моменту К[j/2] ³ Кj при l < [j/2] < j £ r (4), а записи Rk, r < k £ N, занимают свои окончательные места. Шаги У3–У8 называют алгоритмом "протаскивания"; их действие эквивалентно установке R l = R с последующим перемещением записей R l,…,Rr таким образом, чтобы условие (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.
(Поднять его вверх). Установить Ri:=Rj и возвратиться к шагу У4.
– алгоритм
(Занести R) Установить Ri:= 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 }
Дата публикования: 2015-01-10; Прочитано: 281 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!