Методы программирования. Громов Ю.Ю - 79 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

79
Рис. 32. Последовательное распределение памяти
для полного бинарного дерева с 16 узлами
Заметим, что отцом узла номер k является узел с номером
2/k
, а
его потомками – узлы с номерами 2k и 2k + 1.
Наконец рассмотрим нисходящий метод сортировки, который обхо-
дится совсем без ключей «–
∞», т.е. вся существенная информация,
имеющаяся на рис. 31, располагается в ячейках 1 – 16 полного бинарного
дерева без всяких бесполезных ячеек, содержащих «–
∞». Этот метод,
называемый пирамидальной сортировкой, сортирует N записей на том же
месте в памяти без вспомогательной области вывода.
Файл ключей K
1
, K
2
, …, K
N
будем называть пирамидой, если
2/j
K
≥ K
j
при 1 ≤
2/
j
< j ≤ N. (49)
В этом случае K
1
≥ K
2
, K
1
≥ K
3
, K
2
≥ K
4
и т.д. (см. рис. 31), т.е. наи-
больший ключ оказывается на вершине пирамиды:
K
1
= max (K
1
, K
2
, …, K
N
). (50)
Рассмотрим задачу преобразования произвольного исходного файла
в пирамиду. Пусть нам удалось расположить файл таким образом, что:
2/j
K
≥ K
j
при l <
2/
j
< j ≤ N, (51)
где l ≥ 1. Заметим, что в исходном файле это условие выполняется «авто-
матически» для l =
2/
N
, поскольку ни один индекс j не удовлетворяет
условию
NjjN
≤<< 2/2/
. Нетрудно понять, как, изменяя лишь
поддерево с корнем в узле l, преобразовать файл, чтобы распространить
неравенства (51) и на случай, когда
2/
j
= l. Следовательно, можно
уменьшать l на единицу до тех пор, пока в конце концов не будет достиг-
нуто условие (49). Эти идеи приводят к изящному алгоритму, который
заслуживает пристального изучения.
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17
18 19
20 21 22 23 24 25 26 27 28 29 30 31

Страницы