Массив М

номер элемента массива М
значение элемента массива М

1

2 3

4 5 6 7

8 9

Рис. 7. Дерево массива М

Дерево на рис.7 не является пирамидой, но левое и правое поддерево — пирамиды. Для того, чтобы это дерево перестроить в пирамиду, достаточно значение из корня дерева «опустить вниз» меняя его местами с сыном, имеющим наибольшее значение. Обмен производить до тех пор, пока есть сын, больший, чем элемент в корне. При перестроении дерева на рис.7 в пирамиду на рис.8 корневой элемент опускается на седьмой, а третий и седьмой поднимаются соответственно на первый и третий. Пирамида построена и теперь корень можно поменять с последним элементом дерева и в дальнейшем его не обрабатывать. Для полной сортировки процесс повторяется, пока в дереве количество вершин больше одного.

1

2 3

4 5 6 7

8 9

Рис. 8. Пирамида для массива М

Сформулируем алгоритм перестроения дерева, у которого левое и правое поддерево — пирамиды, в пирамиду.

Алгоритм MakeHeap.

1. Запоминаем корневой элемент.

2. Перебираем элементы в направлении большего сына и сдвигаем каждый элемент “вверх” на одну позицию, пока не освободится место для корневого элемента.

3. Вставляем корневой элемент на освободившееся место.

Для построения пирамиды из произвольного дерева (массива) необходимо построить пирамиду по алгоритму MakeHeap для каждого элемента, имеющего хотя бы одного сына, причем построение должно идти от последнего такого элемента к первому, т.е. снизу вверх.

Теперь можем сформулировать алгоритм пирамидальной сортировки.

Алгоритм HeapSort.

1. Построить пирамиду для исходного массива.

2. Пока в массиве более одного элемента, переставить первый и последний элемент, уменьшить размер массива на единицу и перестроить дерево в пирамиду по алгоритму MakeHeap.

Анализ пирамидальной сортировки

Пусть дерево массива на нижнем (нулевом) уровне содержит максимальное число вершин. Для построения пирамиды из произвольного дерева (первая часть алгоритма) нужно обработать все вершины, начиная с первого уровня. Для обработки вершины на i-том уровне число сравнений пропорционально i. Число вершин на i-том уровне равно 2^[log2N]-1, а всего уровней m=[log₂N], следовательно, общее число сравнений определяется формулой: 1·2^[log2N]-1 + 2·2^[log2N]-2 + … + m·2^[log2N]-m = O(N).

Во второй части алгоритма последовательно обрабатываются деревья с N, N – 1, …,2 вершинами. Число сравнений для перестройки дерева, состоящего из i вершин, в пирамиду пропорционально [log₂i], следовательно, общее число сравнений

[log ₂ N] + [log ₂ (N – 1)] + … + [log ₂ 2] = O(N·log ₂ N).

Таким образом порядок функции ВС алгоритма пирамидальной сортировки O(N·log₂N).