Стр. 88 - Основы алгоритмов и структур данных

86 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
от шага к шагу сам массив X таким образом, чтобы в его структуре легко было
выделить X’,X’’… . Это легко сделать, если элементы X своей структурой
образуют пирамиду.
5.3.1. Пирамидальная сортировка
Пирамида — это полностью сбалансированное бинарное дерево высоты h,
в котором все листья находятся на расстоянии h или (h – 1) от корня и все
потомки узла меньше его самого; кроме того, в нем все листья уровня h
максимально смещены влево.
Например, для массива
91 48 58 94 34 18 85 93 10 75 51 44
пирамида может принять следующий вид:
94
93 75
91
18
85
58 48 10
44
34
51
Рис. 69. Пирамида
В памяти дерево можно представить одномерным массивом, используя
следующие правила: корень записывается в 1-ю позицию; если некоторый узел
записан в позицию i, то его левый сын пишется в позицию 2i, а правый – (2i+1).
Таким образом, приведённая пирамида запишется следующим образом:
1 2 3 4 5 6 7 8 9 10 11 12
94 93 75 91 85 44 51 18 48 58 10 34
Сортировка пирамиды в порядке возрастания ключей осуществляется
следующим образом:
шаг 1. Наибольшее имя (оно всегда первое) помещаем в последнюю
позицию.
n x x ↔
1
шаг i ( i=2,…,n). После обмена, произведённого на шаге (i-1) пирамида
может быть испорчена (например, после первого шага первым стоит не
наибольший ключ 34). Тогда восстанавливаем пирамиду. Корень её
переставляем в i-ю позицию с конца.
i n x x−+ ↔ 1 1 .
Таким образом, имеем алгоритм: