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

Описанное здесь сортировка в среднем медленнее, чем быстрое, хотя и имеет сложность в наиболее плохом случае B(n\ogn) . Тем не менее этот алгоритм применяется для сортировки файлов и решение некоторых других задач. Пирамидальная сортировка (или сортировка с помощью груды) использует бинарное дерево (пирамиду). Рассмотрим цс понятие. Расположим элементы массива с индексами 1..к строками, удваивая количество элементов в строках: в первой строке — первый элемент (с индексом 1), во второму — с индексами 2 и 3, в третьему — с индексами 4-7, дальше— 8-15 и т.п.. Последняя строка может остаться неполным, Например, при п = 10 будет образована пирамида индексов, как на рисунке.

Рассмотрим пирамиду как бинарное дерево с корнем наверху и листвой внизу. Дерево образовано узлами, которые відловідають индексам, и связями между ними — дугами. Корнем дерева является узел 1. Узлы 2 и С назовем сыновьями узла І (их отца), узлы 4 и 5 — сыновьями 2 и т.п.. Узлы, которые не имеют сынов, называются листками (на рисунке это узлы 6-10. Итак, если узел и имеет сынов, то ими есть узлы с индексами 11 и 2/ + 1, а его отцом является узел с индексом / div 2.

Дальше будем рассматривать узлы дерева, которые содержат значение элементов массива с соответствующими индексами, Для сортировки важным есть упорядочения значений в массиве, за который при каждому возможному и исполняется неровность А\\ div 2] >/4[j], т.е. «сын не больше отца». Это свойство не касается лишь корня дерева, поскольку он не имеет отца. Дерево с этим свойством называют правильным, или правильной грудой. Рассмотрим пример правильного дерева, которое отвечает последовательности значений

Сортировка с помощью груды использует то, что корень правильной груды содержит ее максимальное значение. Сначала в массиве образуем правильную груду, дальше поменяем местами значения первого элемента массива (корня дерева) и последнего. Наибольшее значение займет «свое» последнее место в массиве, и дальше о нем можно забыть. Среди сдачи элементов массива восстановим основное свойство груды и обменяем местами значения первого элемента и теперь уже предпоследнего, и так будем действовать дальше, пока дерево не сократится до одного элемента. procedure heapSort(var A:alnt; n:word);

var j:word; {индекс последнего} begin

build(A,n); {начальное построение хупи} for j:=n downto 2 do begin swap(A[l],A[j]);

rebuild(A,1,j-1) {восстановление правильности} end end;

Сначала уточним процедуру rebuild восстановление правильности груды. Если значение в корневом узле изменилось, основное свойство в нем может не выполняться, поэтому по потребности больший из сынов обменивается с отцом, после чего основное свойство проверяется и восстанавливается для сына. Действия из восстановление правильности груды в части массива А]/], …, A[d] нетрудно уточнить рекурсивной процедурой.

procedure rebuild(var A:alnt; f,d:word); var maxSon:word; {индекс максимального сына} begin
maxSon:=f;
if (2*f<=d)and(A[f]<A[2*f])
then maxSon := 2*f;
if (2*f+K=d) and(A[maxSon]<A[2*f+1])
then maxSon:=2*f+1; if maxSonOf then begin swap(A[f] r[maxSon]) ; rebuild<A,maxSon,d); end; end;
Приведенная процедура является примером так называемой «хвостовой ре-курсії», когда после рекурсивного вызова нет никаких действий. В подобных ситуациях рекурсию можно заменить циклом, условие завершения которого отвечает условию «дна рекурсн». Очевидно также, что перестройку дерева можно закончить, если значение максимального сына и отца местами не обменивались. В этой ситуации, чтобы прекратить выполнение цикла, присвоим индекса «отца» f значение за пределами части массива, который перестраивается. Итак, приведем нерекурсивный вариант процедуры rebuild, procedure rebuild(var A.alnt; f,d:word); var maxSon:word; {индекс максимального сына} begin
while (2*f<=d)do begin
maxSon:=f;
if <M?]<A[2*ff]) then maxSon:=2*f;
if (2*f+K=d)andCA[raaxSon]< A[2*f+1]) then maxSon:=2*f+l; if maxSonOf then begin swap(A[f],A[maxSon]);
f :=maxSon -{дальше перестройка пирамиды сына} end
else f:=d+l; end;
{2*f > d или A[f] >= A[maxSon]} end;

В конце концов уточним начальное построение груды за процедурой build. Заметим, что в массиве с п элементами максимальным ‘индексом узла-отца есть п div 2. Итак, последовательно образуем правильные груды в піддеревах, корнями которых являются узлы п div 2, п div 2 — и,…, 1. Это разрешит утверждать, что построенный массив представляет собой правильную груду.

procedure build(var A:alnt; n:word); var и:word;
begin
for i:=n div 2 downto 1 do
rebuild(A,i,n); {перестройка чаотини массива}
end;

Оценим сложность алгоритма. Очевидно, что она прямо пропорциональная общему количеству вызовов rebuild. При выполнении build процедура rebuild вызывается п div 2 раза, а при выполнении цикла for процедуры treeSort — еще л — 2 раза, т.е. общее количество вызовов процедуры rebuild из других процедур есть ®(п).

Оценим сложность выполнения одного вызова процедуры rebuild. Заметим, что в цикле значения сменной f не менее чем удваивается, а цикл не будет продлеваться, если это значение станет больше d, которое не больше г. Итак, таких удвоений не может быть больше чем |_log2 п\ . Количество действий в теле цикла является константой, поэтому общая сложность имеет оценку 0{n\ogn). Высотой узла дерева называют количество ребер в наиболее длинном пути из этой вершины вниз к листкам; высоту корня называют высотой дерева. Дерево, которое образовано как пирамида с п узлов, имеет высоту log2 п .