Hачать построение пирамиды можно с a[k]. .a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i, j: i = 2i+1 (или j = 2i+2)… Просто потому, что такие i, j находятся за границей массива.
Следует заметить, что неправильно говорить о том, что a[k]. .a[n] является пирамидой как самостоятельный массив. Это, вообще говоря, не верно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива a[0]. .a[n].
Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления — тот, который стоит перед уже готовой частью.
Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]. .a[n] на элемент a[i] влево:
1. Смотрим на сыновей слева и справа — в массиве это a[2i+1] и a[2i+2] и выбираем наибольшего из них.
2. Если этот элемент больше a[i] - меняем его с a[i] местами и идем к шагу 2, имея в виду новое положение a[i] в массиве. Иначе конец процедуры.
Новый элемент «просеивается» сквозь пирамиду.
Ниже дана иллюстрация процесса для пирамиды из 8-и элементов:
44 55 12 42 // 94 18 06 67 Справа — часть массива, удовлетворяющая
44 55 12 // 67 94 18 06 42 свойству пирамиды,
44 55 // 18 67 94 12 06 42
44 // 94 18 67 55 12 06 42 остальные элементы добавляются
// 94 67 18 44 55 12 06 42 один за другим, справа налево.
В геометрической интерпретации ключи из начального отрезка a[size/2]. .a[n] является листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так — пока не будет построена вся пирамида.
На рисунках ниже изображен процесс построения. Неготовая часть пирамиды (начало массива) окрашена в белый цвет, удовлетворяющий свойству пирамиды конец массива — в темный.
Фаза 2: собственно сортировка
Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:
1. Берем верхний элемент пирамиды a[0]. .a[n] (первый в массиве) и меняем с последним местами. Теперь «забываем» об этом элементе и далее рассматриваем массив a[0]. .a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.
2. Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.
Очевидно, в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.
94 67 18 44 55 12 06 42 // иллюстрация 2-й фазы сортировки
67 55 44 06 42 18 12 // 94 во внутреннем представлении пирамиды
55 42 44 06 12 18 // 67 94
44 42 18 06 12 // 55 67 94
42 12 18 06 // 44 55 67 94
18 12 06 // 42 44 55 67 94
12 06 // 18 42 44 55 67 94
06 // 12 18 42 44 55 67 94
Каково быстродействие получившегося алгоритма ?
Построение пирамиды занимает O (n log n) операций, причем более точная оценка дает даже O (n) за счет того, что реальное время выполнения зависит от высоты уже созданной части пирамиды.
Вторая фаза занимает O (n log n) времени: O (n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.
Пирамидальная сортировка не использует дополнительной памяти.
Метод не является устойчивым: по ходу работы массив так «перетряхивается», что исходный порядок элементов может измениться случайным образом.
Поведение неестественно: частичная упорядоченность массива никак не учитывается.
