Стр. 87 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
85
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Заметим, что для определения наибольшего имени этот процесс требует
(
n
– 1) сравнений имен, но, определив наибольшее имя, мы обладаем большим
объемом информации о втором по величине (в порядке убывания) имени: оно
должно быть одним из тех, которые «потерпели поражение» от наибольшего
имени. Таким образом, второе по величине имя теперь можно определить,
заменяя наибольшее имя на – ∞ и вновь осуществляя сравнение вдоль пути от
наибольшего имени к корню. Далее эта процедура показана для предыдущего
дерева.
X
1
= 91
X
2
= 15
X
3
= 48
X
4
= 58
X
5
= 63
X
6
= -∞
X
7
= 34
X
8
= 8
X
9
= 85
X
10
= 93
X
11
= 10
X
12
= 3
X
13
= 13
X
14
= 75
X
15
= 51
X
16
= 44
91
58
63
34
93
10
75
51
91
63
93
75
91
93
93
X
’
X
’’
X
’’’
Рис. 68. Выбор второго по величине элемента
Поскольку дерево имеет высоту [log
2
n
], второе по величине имя можно
найти за [log
2
n
] – 1 сравнений, вместо (
n
– 2), используемых в алгоритме
простого выбора. Этот процесс, очевидно, можно продолжить. Найдя второе по
величине имя, заменяем его на — ∞ и делаем вновь [log
2
n
] – 1 сравнений, чтобы
найти следующее, и т. д. Таким образом, в целом процесс использует
следующее количество сравнений имён:
n n n
n
n C
2
2
log
log )1 ( )1 (
≈
− +− =
.
Это значение не зависит от исходного порядка ключей и соответствует
значению, полученному для быстрой сортировки. Однако в описанном виде
метод неприемлем, так как для хранения вспомогательных массивов (а точнее
индексов ключей)
X
’,
X
’’ и т.д. потребует
n
дополнительных ячеек памяти.
Поскольку
X
’,
X
’’ и т.д являются подмножествами
X
, то возникает идея:
вместо выделения дополнительных ячеек
X
’,
X
’’ …, будем переформировывать
