Пирамидальная сортировка

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

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

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

а_i <= а_2i и а_i <= а_2i+1

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

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

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

Это – пирамида. Соответствующий массив: 15-25-20-30-40-22-33-50-60-45-47-44-28-55-66	Это – не пирамида (вершина 12 меньше 20)

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

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

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

· на вершине пирамиды всегда находится наименьший элемент во всем массиве (элемент а₁), элемент а₂ является наименьшим для левого поддерева, элемент а₃ является наименьшим для правого поддерева и т.д.

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

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

· представление исходного массива в виде пирамиды

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

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

· условно разделяем исходный массив на две половины: левую с индексами от 1 до [n/2], и правую с индексами от [n/2]+1 до n (здесь [ ] обозначает целую часть); считаем пока, что левая половина образует верхнюю часть строящейся пирамиды, а правая – нижний слой терминальных вершин

· выбираем в левой половине последний элемент (его индекс m=[n/2]), а в правой половине – его непосредственных потомков (одного или двух, но хотя бы один будет обязательно) с индексом 2m и, возможно, 2m+1

· если потомков два, то выбираем из них наименьшего

· сравниваем элемент а_m с наименьшим из потомков: если он больше, то меняем эти элементы в массиве местами для получения фрагмента пирамиды; в противном случае оставляем все без изменений, поскольку эти элементы уже образуют фрагмент пирамиды

· повторяем все описанные действия последовательно для оставшихся в левой части элементов справа налево, т.е. для а_m-1, а_m-2, а_m-3, . . ., а₁, при этом если происходит обмен между родительской вершиной и одним из потомков, выполняется проверка для новой вершины-потомка, т.к. она может иметь своих потомков, с которыми возможно потребуется ее обменять для выполнения условия пирамиды.

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

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

а15

сравнение и обмен

33

33> min(20, 50), 33~20

44< min(47, 66), нет

30

30> min(15, 55), 30~15

25

25> min(22, 60), 25~22

28

28>min(44, 20), 28~20

28<min(33, 50), нет

40

40>min(22, 15), 40~15

40

40>min(30, 55), 40~30

45

45>min(15, 20), 45~15

45

45>min(22, 30), 45~22

45

45>min(25, 60), 45~25

Пирамида построена

В худшем случае каждый шаг в просеивании очередного элемента требует двух сравнений: сначала сравниваются два потомка текущего элемента, а потом наименьший из них сравнивается с самим элементом. В примере для построения пирамиды потребовалось 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;