Древесная сортировка

При использовании этой сортировки в массиве постоянно поддерживается такой порядок, при котором максимальный элемент всегда будет оказываться в A[1]. Сортировка называется древесной, потому что в этом методе используется структура данных, называемая двоичным деревом. При чем используется представление дерева в виде массива (см. п. 2.3.4.4) и при сортировке используется тот же способ расположения вершин дерева в массиве.

Пусть A[1]...A[n] – массив, подлежащий сортировке. Вершинами дерева будут числа от 1 до n; о числе A[i] будем говорить как о числе, стоящем в вершине i. В процессе сортировки количество вершин дерева будет сокращаться. Число вершин текущего дерева будем хранить в переменной k. Таким образом, в процессе работы алгоритма массив A[1]...A[n] делится на две части: в A[1]...A[k] хранятся числа на дереве, а в A[k+1]...A[n] хранится уже отсортированная в порядке возрастания часть массива – элементы, уже занявшие свое законное место.

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

Договоримся о терминологии. Вершинами дерева считаются числа от 1 до текущего значения переменной k. У каждой вершины s могут быть потомки 2s и 2s+1. Если оба этих числа больше k, то потомков нет; такая вершина называется листом. Если 2s=k, то вершина s имеет ровно одного потомка (2s).

Для каждого s из 1...k рассмотрим «поддерево» с корнем в s: оно содержит вершину s и всех ее потомков. Вершина s называется регулярной, если стоящее в ней число – максимальный элемент s-поддерева; s-поддерево называется регулярным, если все его вершины регулярны. В частности, любой лист образует регулярное одноэлементное поддерево.

Теперь запишем алгоритм сортировки:

procedure TreeSort (n: integer;

var A: array[1..n] of integer);

{Процедура древесной (пирамидальной) сортировки}

var

u, k: integer;

procedure Exchange(i, j: integer);

{Процедура обмена двух элементов}

var

Tmp: integer;

begin

Tmp := A[i];

A[i] := A[j];

A[j] := Tmp;

end; {Exchange}

procedure Restore(s: integer);

{Процедура восстановления регулярности поддерева с корнем s}

var

t: integer;

begin

t:=s; {начинаем с корня поддерева}

while ((2*t+1 <= k) and (A[2*t+1] > A[t])) or

((2*t <= k) and (A[2*t] > A[t])) do begin

{Пока не просмотрено все поддерево и вершина t нерегулярна}

if (2*t+1 <= k) and (A[2*t+1] >= A[2*t]) then begin

{Меняем корень поддерева с его правым потомком}

Exchange(t, 2*t+1);

t := 2*t+1; {переход к правому потомку}

end else begin

{Меняем корень поддерева с его левым потомком}

Exchange(t, 2*t);

t := 2*t; {переход к правому потомку}

end;

end;

end; {Restore}

begin

k:=n;

u:=n;

while u <> 0 do begin

Restore(u);

u := u - 1;

end;

while k <> 1 do begin

Exchange(1, k);

k := k - 1;

Restore(1);

end;

end; {TreeSort}

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

Рисунок 44. Древесная сортировка

Рассмотрим восстановление регулярности подробнее. Пусть в s-поддереве все вершины, кроме разве что вершины t, регулярны. Рассмотрим потомков вершины t. Они регулярны, и потому содержат наибольшие числа в своих поддеревьях. Таким образом, на роль наибольшего числа в t-поддереве могут претендовать число в самой вершине t и числа, содержащиеся в ее потомках (в первом случае вершина t регулярна, и все в порядке).

После обмена вершина t становится регулярной (в нее попадает максимальное число t-поддерева). Не принявший участия в обмене потомок остается регулярным, а принявший участие может и не быть регулярным. В остальных вершинах s-поддерева не изменились ни числа, ни поддеревья их потомков (разве что два элемента поддерева поменялись местами), так что регулярность не нарушилась.

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

Преимущество этого алгоритма перед другими в том, что он, имея максимальную временную сложность T_max(n), пропорциональную O(n*log n) (внутри внешнего цикла зависящего от n линейно вызывается процедура Restore, требующая порядка log n действий), не требует дополнительной памяти порядка O(n).