Пирамидальная сортировка
Назовем пирамидой последовательность элементов
hl , hl+1 , ... , hr
такую, что
hi <= h2i
hi <= h2i+1
для всякого i = l , ... , r/2
Геометрическая интерпретация пиромиды:
h1
/ \
/ \
/ \
/ \
/ \
h2 h3
/ \ / \
/ \ / \
h4 h5 h6 h7
/ \ / \ / \ / \
h8 h9 h10 h11 h12 h13 h14 h15
Для последовательности 06 42 12 55 94 18 44
06
/ \
/ \
/ \
/ \
/ \
42 12
/ \ / \
/ \ / \
55 94 18 44
Добавление элемента в готовую пирамиду
1. Новый элемент Х помещаем в вершину дерева.
2. Смотрим на элемент слева и элемент справа - выбираем наименьший.
3. Если этот элемент меньше Х - меняем их местами и идем у шагу 2. Иначе конец процедуры.
Фаза 1: построение пирамиды
Пусть дан массив h1 ... hn . Ясно, что элементы hn/2 + 1 ... hn уже образуют 'нижний ряд' пирамиды, так как не существует индексов i , j : j = 2*i ( или j = 2*i + 1 ). То есть тут упорядочивания не требуется.
На каждом шаге добавляется новый элемент слева и 'просеивается' на место. Вот иллюстрация процесса для пирамиды из 8-и элементов:
44 55 12 42 // 94 18 06 67 44 55 12 // 42 94 18 06 67 44 55 // 06 42 94 18 12 67 44 // 42 06 55 94 18 12 67 // 06 42 12 55 94 18 44 67
Фаза 2: сортировка
Для того, чтобы рассортировать элементы, необходимо выполнить n шагов просеивания: после каждого шага очередной элемент берется с вершины пирамиды. На каждом шаге берем последний элемент Х, верхний элемент пирамиды помещается на его место, а Х просеивается на свое 'законное'. В этом случае необходимо совершить n - 1 шагов. Пример:
06 42 12 55 94 18 44 67 // 12 42 18 55 94 67 44 // 06 18 42 44 55 94 67 // 12 06 42 55 44 67 94 // 18 12 06 44 55 94 67 // 42 18 12 06 55 67 94 // 44 42 18 12 06 67 94 // 55 44 42 18 12 06 94 // 67 55 44 42 18 12 06Ну вот мы м получили отсортированную последовательность, только в обратном порядке. Изменяя сравнения на противоположные, получаем функцию Heapsort на Паскале
Прекрасной характеристикой этого метода является то, что среднее число пересылок - (n*log n)/2 и отклонения от этого значения сравнительно малы.
