Стр. 90 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
88
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
94
93
58
91
48
34
75
10
51
18
44
85
Рис. 71. Бинарное дерево
Таким образом, процедура восстановления пирамиды из бинарного дерева,
у которого в корне стоит не больший ключ, но оба поддерева являются
пирамидами, имеет вид
restore(x, j, k) // x –массив, j, k – начальный и конечный
//индексы для восстановления
// тривиальный случай – j – лист
restore(x, j, k)
{
if not (j – лист)
{
m= <индекс большего из x
2
j
, x
2
j+1
>
if (x
m
> x
j
)
{
< меняем x
m
и x
j
>
restore(x, m, k);
}
}
}
// заметим, что j – не лист, если j<=k/
2
.
restore(x, j, k)
{
m= <индекс большего из x
2
j
, x
2
j+1
>
while (j<=k/
2
)
{
if ((
2
j<k) && (x
2
j
<x
2
j+1
)) m=
2
j+1;
else m=
2
j;
if (x
m
>x
j
)
{
< меняем x
m
и x
j
>;
j=m;
}
else return;
}
}
