Стр. 91 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
89
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Начальное построение пирамиды
Вначале все дерево и его поддеревья не являются пирамидами, за
исключением поддеревьев, корнями которых являются листья. Начнем с
последней вершины, которая не является листом. Индекс той вершины
n
/2.
Дерево с этим корнем в качестве поддеревьев уже имеет пирамиды. Осталось
вызвать процедуру restore(
x
,
n
/2,
n
). Далее аналогичным образом
восстанавливаем пирамиды для вершин
n
/2-1,
n
/2-2,
n
/2-3, …, 1.
Окончательный вариант пирамидальной сортировки имеет следующий вид:
for (i=n/
2
; i>=
1
; i--)
{
restore(x, i, n); //фаза построение
}
for (i=n; i>=
2
; i--)
{
< меняем x
1
и x
i
> //фаза выбора пирамиды
restore(x,
1
, i-
1
);
}
Анализ быстродействия
. Оценим затраты на выполнение restore(
x
,
j
,
n
).
Если поддерево содержит
f
элементов, начиная с 1, то высота этого дерева log
2
f
.
restore выполняет столько операций (в худшем случае), какова разность высот j
и k, то есть log
2
k
– log
2
j
= = log
2
(
k/j
).
На каждом уровне рекурсии restore происходит 2 сравнения и не более 1-й
перестановки. Таким образом, в худшем случае на всех
n
/2 итерациях фазы
построения перестановок будет (сумма по
i
):
)(
)
2
1( log
log
2
1
log
П
2/
1
2
2
2
постр
nO n
n n
i
n
n
i
=
−
=
=
∑
=
.
На на фазе выбора (
i
от 2 до
n
) перестановок происходит не более:
∑
=
+
≈
−
+− =
n
i
nOn n
i
n
2
2
2
выбор
)(
log )
1
1 ( log
)1 (
П
.
В худшем случае число перестановок:
П
постр
+П
выбор
=
О
(
n
) +
n
log
2
n
+
O
(
n
) =
O
(
n
log
2
n
).
Это лучшее быстродействие в худшем из случаев среди всех алгоритмов
сортировки. Пирамидальную сортировку следует использовать, когда требуется
гарантированно высокое быстродействие для каждого отдельного сеанса
сортировки, например, в программах реального времени.
