Пирамидальная сортировка. 
Структуры и алгоритмы обработки данных

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

Пусть имеется исходный массив n элементов, а ₁ а ₂, а ₃,…, а_n. Расположим эти элементы в виде двоичного дерева следующего вида (здесь важен порядок следования индексов элементов):

Подобное дерево называется пирамидой, если для всех элементов с индексами от 1 до n/2 выполняются следующие условия:

аi <= а2i и аi <= а 2i+1.

В частности, эти условия означают: а ₁ <= а ₂ и, а ₁ <= а ₃; а ₂ <= а ₄ и, а ₂ <= а ₅; а ₃ <= а ₆ и, а ₃ <= а ₇; а ₄ <= а ₈ и, а ₄ <= а ₉, и т. д.

Другими словами, в каждом элементарном поддереве значение в вершине этого поддерева меньше или равно значений в вершинах-потомках.

Пример двоичного дерева-пирамиды с 15-ю элементами:

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

Из примера видно, что пирамида НЕ является деревом поиска, т.к. строится по другим правилам.

Можно отметить следующие полезные свойства пирамиды:

• · на вершине пирамиды всегда находится наименьший элемент во всем массиве (элемент, а ₁), элемент, а ₂ является наименьшим для левого поддерева, элемент, а ₃ является наименьшим для правого поддерева и т. д.
• · вершины, лежащие на самом нижнем уровне пирамиды, всегда образуют из себя элементарные пирамиды, поскольку у них нет никаких потомков и их сравнивать не с кем.

Пирамидальная сортировка включает два больших этапа:

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

Реализация 1 этапа включает следующие шаги:

• · условно разделяем исходный массив на две половины: левую с индексами от 1 до [n/2], и правую с индексами от [n/2]+1 до n (здесь []обозначает целую часть); считаем пока, что левая половина образует верхнюю часть строящейся пирамиды, а правая — нижний слой терминальных вершин
• · выбираем в левой половине последний элемент (его индекс m= [n/2]), а в правой половине — его непосредственных потомков (одного или двух, но хотя бы один будет обязательно) с индексом 2m и, возможно, 2m+1
• · если потомков два, то выбираем из них наименьшего
• · сравниваем элемент а_m с наименьшим из потомков: если он больше, то меняем эти элементы в массиве местами для получения фрагмента пирамиды; в противном случае оставляем все без изменений, поскольку эти элементы уже образуют фрагмент пирамиды
• · повторяем все описанные действия последовательно для оставшихся в левой части элементов справа налево, т. е. для а_m-1, а_m-2, а_m-3,…, а ₁, при этом если происходит обмен между родительской вершиной и одним из потомков, выполняется проверка для новой вершины-потомка, т.к. она может иметь своих потомков, с которыми возможно потребуется ее обменять для выполнения условия пирамиды.

Тем самым, для каждого элемента массива находится его новое расположение в массиве таким образом, чтобы выполнялись условия пирамиды. Процесс определения нужного положения элемента в массиве-пирамиде называют просеиванием элемента через пирамиду. Построение пирамиды заканчивается после просеивания первого элемента, а ₁. Пример для 15 элементов приведен в таблице (символ ~ обозначает перестановку элементов).

В худшем случае каждый шаг в просеивании очередного элемента требует двух сравнений: сначала сравниваются два потомка текущего элемента, а потом наименьший из них сравнивается с самим элементом. В примере для построения пирамиды потребовалось 11*2=22 сравнения и 9 пересылок.

Реализация второго этапа состоит в (n-1)-кратном повторении следующих действий:

• · с вершины пирамиды забирается минимальный элемент, а ₁
• · на его место в вершину пирамиды помещается последний элемент в массиве, причем индекс этого последнего элемента на каждом шаге будет уменьшаться от а_n до, а ₂
• · помещенный в вершину элемент просеивается через пирамиду обычным образом, при этом он встает на свое место, а в вершину пирамиды выталкивается минимальный из оставшихся в массиве элементов
• · на последнем шаге в пирамиде останется один элемент (самый большой) и сортировка будет закончена.

При этом возникает вопрос — куда девать снимаемые с вершины пирамиды элементы? Можно просто помещать их в конец массива на место элемента, размещаемого в вершине. В результате на месте исходного массива создается упорядоченный ПО УБЫВАНИЮ набор данных. При необходимости, алгоритм легко можно изменить для получения возрастающих последовательностей, если вместо минимальных использовать максимальные пирамиды.

В данном примере выполнено 51 сравнение и 40 пересылок, что вместе с этапом построения пирамиды дает 73 сравнения и 49 пересылок.

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

В [4] указывается, что пирамидальную сортировку выгодно использовать в том случае, когда требуется не провести полную сортировку большого набора данных, а лишь найти несколько (причем — немного) первых наименьших элементов.

Необходимо отметить, что понятие пирамидального дерева имеет и самостоятельное значение, и часто используется для решения других задач, не связанных с сортировкой массивов, например — для эффективной реализации приоритетных очередей [4].

В заключение рассмотрим вопросы программной реализации пирамидальной сортировки. Поскольку оба этапа алгоритма основаны на повторении одинаковых действий по просеиванию элементов, удобно оформить просеивание в виде вспомогательной процедуры.

Procedure Sito (al, ar: word);

var i, j: word;

x: ;

begin.

i:= al; j:= 2*al; x:= mas [al];

if (j < ar) and (mas [j + 1]< mas [j]) then j:= j + 1;

while (j <=ar) and (mas [j]< x) do.

begin.

mas [i]: = mas [j]; i:=j; j:=2*j;

if (j < ar) and (mas [j + 1]< mas [j]) then j:= j + 1;

end;

mas [i]: = x;

end;

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

left:= (n div 2) + 1; right:= n;

{определение границ правой половины массива}.

while left > 1 do.

begin {цикл построения пирамиды}.

left:= left — 1; Sito (left, right);

end;

while right > 1 do (цикл сортировки}.

begin.

temp:= mas [1]; mas [1]: = mas [right]; mas [right]: = temp;

right:= right — 1; Sito (left, right);

end;