Пирамидальная сортировка. 
Исследование методов сортировки выбором

Пирамидальная сортировка является методом, быстродействие которого оценивается как О (n log n). В качестве некоторой прелюдии к основному методу, рассмотрим перевернутую сортировку выбором. Во время прохода, вместо вставки наименьшего элемента в левый конец массива, будем выбирать наибольший элемент, а готовую последовательность строить в правом конце.

Рисунок 2. Пример действия массива а[0]…a[7].

Вертикальной чертой отмечена левая граница уже отсортированной (правой) части массива. Рассмотрим оценку количества операций подробнее. Всего выполняется n шагов, каждый из которых состоит в выборе наибольшего элемента из последовательности a[0]…a[i] и последующем обмене. Выбор происходит последовательным перебором элементов последовательности поэтому необходимое на него время: O (n). Итак, n шагов по О (n) каждый — это О).

Произведем усовершенствование: построим структуру данных, позволяющих выбирать максимальный элемент последовательности не за O (n), а за O (logn) времени. Тогда общее быстродействие сортировки будет.

n*O (logn) = O (n log n)

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

Итак назовем пирамидой бинарное дерево высоты k, в котором:

• · все узлы имеют глубину k или k-1 — дерево сбалансированное.
• · при этом уровень полностью заполнен, а уровень k заполнен слева направо.
• · выполняется свойство пирамиды: каждый элемент меньше, либо равен родителю.

Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме на рисунке 3.

• · в а[0] хранится корень дерева
• · левый и правый сыновья элемента a[i] хранятся, соответственно, в a[2i+1 и a[2i+2]

Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i]>=a[2i+1] и a[i]>=a[2i+2].

Плюсы такого хранения пирамиды очевидны:

• · никаких дополнительных переменных, нужно лишь понимать схему
• · узлы хранятся от вершины и далее вниз, уровень за уровнем.
• · узлы одного уровня хранятся в массиве слева направо

Запишем в виде массива пирамиду, изображенную выше. Слева-направо, сверху-вниз: 94 67 18 44 55 12 06 42. На рисунке 3 место элемента пирамиды в массиве обозначено цифрой справа-вверху от него.

Восстановить пирамиду из массива как геометрический объект легко — достаточно вспомнить схему хранения и нарисовать, начиная от корня.

Начать построение пирамиды можно с a[k]…a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i, j: i=2i+1 (или j = 2i+2). Такие i, j находятся за границей массива.

Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления — тот, который стоит перед уже готовой частью.

Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]. .a[n] на элемент 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] являются листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так — пока не будет построена вся пирамида.

Неготовая часть пирамиды (начало массива) окрашена в белый цвет, удовлетворяющий свойству пирамиды конец массива — в темный.

Рисунок 4. Процесс построения пирамиды.

Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:

• · Берем верхний элемент пирамиды a[0]…a[n] (первый в массиве) и меняем с последним местами. Теперь «забываем» об этом элементе и далее рассматриваем массив a[0]…a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.
• · Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.

Рисунок 5. Просеивание элементов массива

Очевидно, что в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.

Рисунок 6. Иллюстрация 2-й фазы сортировки во внутреннем представлении пирамиды.

Построение пирамиды занимает О (n log n) операций, причем более точная оценка дает даже О (n) за счет того, что реальное время выполнения зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O (n log n) времени: O (n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

Пирамидальная сортировка не использует дополнительной памяти. Метод не является устойчивым: по ходу работы массив так «перетряхивается», что исходный порядок элементов может измениться случайным образом, частичная упорядоченность массива никак не учитывается.