Сортировка частично упорядоченным деревом.

В двоичном дереве, которое строится в этом методе сортировки для каждого узла справедливо следующее утверждение: значения ключа, записанное в узле, меньше, чем ключи его потомков. Для полностью упорядоченного дерева имеются требования к соотношению между ключами потомков. Для данного дерева таких требований нет, поэтому такое дерево и называется частично упорядоченным. Кроме того, наше дерево должно быть абсолютно сбалансированным. Это означает не только то, что длины путей к любым двум листьям различаются не более, чем на 1, но и то, что при добавлении нового элемента в дерево предпочтение всегда отдается левой ветви/подветви, пока это не нарушает сбалансированность. Более подробно деревья рассматриваются в гл.6.

Например, последовательность чисел:

3 20 12 58 35 30 32 28

будет представлена в виде дерева, показанного на рис.3.15 .

Рис.3.15. Частично упорядоченное дерево

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

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

Алгоритм вставки состоит в следующем. Новый элемент вставляется на первое свободное место за концом дерева (на рис.3.15 это место обозначено символом "*"). Если ключ вставленного элемента меньше, чем ключ его предка, то предок и вставленный элемент меняются местами. Ключ вставленного элемента теперь сравнивается с ключом его предка на новом месте и т.д. Сравнения заканчиваются, когда ключ нового элемента окажется больше ключа предка или когда новый элемент "выплывет" в вершину пирамиды. Пирамида, показанная на рис.3.15, построена именно последовательным включением в нее чисел из приведенного ряда. Если мы включим в нее, например, еще число 16, то пирамида примет вид, представленный на рис.3.16. (Символом "*" помечены элементы, перемещенные при этой операции.)

Рис.3.16. Частично упорядоченное дерево, включение элемента

Процедура выборки элемента несколько сложнее. Очевидно, что минимальный элемент находится в вершине. После выборки за освободившееся место устраивается состязание между потомками, и в вершину перемещается потомок с наименьшим значением ключа. За освободившееся место перемешенного потомка состязаются его потомки и т.д., пока свободное место не опустится до листа пирамиды. Состояние нашего дерева после выборки из него минимального числа (3) показано на рис.3.17.а.

Рис.3.17. Частично упорядоченное дерево, исключение элемента

Упорядоченность дерева восстановлена, но нарушено условие его сбалансированности, так как свободное место находится не в конце дерева. Для восстановления сбалансированности последний элемент дерева переносится на освободившееся место, а затем "всплывает" по тому же алгоритму, который применялся при вставке. Результат такой балансировки показан на рис.3.17.б.

Прежде, чем описывать программный пример, иллюстрирующий сортировку частично упорядоченным деревом - пример 3.13, обратим внимание читателей на способ, которым в нем дерево представлено в памяти. Это способ представления двоичных деревьев в статической памяти (в одномерном массиве), который может быть применен и в других задачах. Элементы дерева располагаются в соседних слотах памяти по уровням. Самый первый слот выделенной памяти занимает вершина. Следующие 2 слота - элементы второго уровня, следующие 4 слота - третьего и т.д. Дерево с рис.3.17.б, например, будет линеаризовано таким образом:

12 16 28 20 35 30 32 58

В таком представлении отпадает необходимость хранить в составе узла дерева указатели, так как адреса потомков могут быть вычислены. Для узла, представленного элементом массива с индексом i индексы его левого и правого потомков будут 2*i и 2*i+1 соответственно. Для узла с индексом i индекс его предка будет i div 2.

После всего вышесказанного алгоритм программного примера 3.13 не нуждается в особых пояснениях. Поясним только структуру примера. Пример оформлен в виде законченного программного модуля, который будет использован и в следующем примере. Само дерево представлено в массиве tree, переменная nt является индексом первого свободного элемента в массиве. Входные точки модуля:

· процедура InitST - инициализация модуля, установка начального значения nt;

· функция InsertST - вставка в дерево нового элемента; функция возвращает false, если в дереве нет свободного места, иначе - true;

· функция DeleteST - выборка из дерева минимального элемента; функция возвращает false, если дерево пустое, иначе - true;

· функция CheckST - проверка состояния дерева: ключ минимального элемента возвращается в выходном параметре, но элемент не исключается из дерева; а возвращаемое значение функции - 0 - если дерево пустое, 1 - если дерево заполнено не до конца, 2 - если дерево заполнено до конца.

Кроме того в модуле определены внутренние программные единицы:

· функция Down - обеспечивает спуск свободного места из вершины пирамиды в ее основание, функция возвращает индекс свободного места после спуска;

· процедура Up - обеспечивающая всплытие элемента с заданного места.

{===== Программный пример 3.13 =====}

{ Сортировка частично упорядоченным деревом }

Unit SortTree;

Interface

Procedure InitSt;

Function CheckST(var a : integer) : integer;

Function DeleteST(var a : integer) : boolean;

Function InsertST(a : integer) : boolean;

Implementation

Const NN=16;

var tr : array[1..NN] of integer; { дерево }

nt : integer; { индекс последнего эл-та в дереве }

{** Всплытие эл-та с места с индексом l **}

Procedure Up(l : integer);

var h : integer; { l - индекс узла, h - индекс его предка }

x : integer;

begin

h:=l div 2; { индекс предка }

while h > 0 do { до начала дерева }

if tr[l] < tr[h] then begin { ключ узла меньше, чем у предка }

x:=tr[l]; tr[l]:=tr[h]; tr[h]:=x; { перестановка }

l:=h; h:=l div 2; { предок становится текущим узлом }

end

else h:=0; { конец всплытия }

end; { Procedure Up }

{** Спуск свободного места из начала дерева **}

Function Down : integer;

var h, l : integer; { h - индекс узла, l - индекс его потомка }

begin

h:=1; { начальный узел - начало дерева }

while true do begin

l:=h*2; { вычисление индекса 1-го потомка }

if l+1 <= nt then begin { у узла есть 2-й потомок }

if tr[l] <= tr[l+1] then begin { 1-й потомок меньше 2-го }

tr[h]:=tr[l]; { 1-й потомок переносится в текущ.узел }

h:=l; { 1-й потомок становится текущим узлом }

end

else begin { 2-й потомок меньше 1-го }

tr[h]:=tr[l+1]; { 2-й потомок переносится в текущ.узел }

h:=l+1; { 2-й потомок становится текущим узлом }

end;

end

else

if l=nt then begin { 1-й потомок есть, 2-го нет }

tr[h]:=tr[l]; { 1-й потомок переносится в текущ.узел }

Down:=l; Exit; { спуск закончен }

end

else begin { потомков нет - спуск закончен }

Down:=h; Exit;

end;

end; { while }

end; { Function Down }

{** Инициализация сортировки деревом **}

Procedure InitSt;

begin

nt:=0; { дерево пустое }

end; { Procedure InitSt }

{** Проверка состояния дерева **}

Function CheckST(var a : integer) : integer;

begin

a:=tr[1]; { выборка эл-та из начала }

case nt of { формирование возвращаемого значения функции }

0: { дерево пустое } CheckSt:=0;

NN: { дерево полное } CheckSt:=2;

else { дерево частично заполнено } CheckSt:=1;

end;

end; { Function CheckST }

{** Вставка эл-та a в дерево **}

Function InsertST(a : integer) : boolean;

begin

if nt=NN then { дерево заполнено - отказ } InsertST:=false

else begin { в дереве есть место }

nt:=nt+1; tr[nt]:=a; { запись в конец дерева }

Up(nt); { всплытие }

InsertSt:=true;

end;

end; { Function InsertST }

{** Выборка эл-та из дерева **}

Function DeleteST(var a : integer) : boolean;

var n : integer;

begin

if nt=0 then { дерево пустое - отказ } DeleteST:=false

else begin { дерево не пустое }

a:=tr[1]; { выборка эл-та из начала }

n:=Down; { спуск свободного места в позицию n }

if n < nt then begin

{ если свободное место спустилось не в конец дерева }

tr[n]:=tr[nt]; { эл-т из конца переносится на своб.место }

Up(n); { всплытие }

end;

nt:=nt-1;

DeleteSt:=true;

end;

end; { Function DeleteST }

END.

Если применять сортировку частично упорядоченным деревом для упорядочения уже готовой последовательности размером N, то необходимо N раз выполнить вставку, а затем N раз - выборку. Порядок алгоритма - O(N*log2(N)), но среднее значение количества сравнений примерно в 3 раза больше, чем для турнирной сортировки. Но сортировка частично упорядоченным деревом имеет одно существенное преимущество перед всеми другими алгоритмами. Дело в том, что это самый удобный алгоритм для "сортировки on-line", когда сортируемая последовательность не зафиксирована до начала сортировки, а меняется в процессе работы и вставки чередуются с выборками. Каждое изменение (добавление/удаление элемента) сортируемой последовательности потребует здесь не более, чем 2*log2(N) сравнений и перестановок, в то время, как другие алгоритмы потребуют при единичном изменении переупорядочивания всей последовательности "по полной программе".

Типичная задача, которая требует такой сортировки, возникает при сортировке данных на внешней памяти (файлов). Первым этапом такой сортировки является формирование из данных файла упорядоченных последовательностей максимально возможной длины при ограниченном объеме оперативной памяти. Приведенный ниже программный пример (пример 3.14) показывает решение этой задачи.

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

{===== Программный пример 3.14 =====}

{ Формирование отсортированных последовательностей в файле }

Uses SortTree;

var x : integar; { считанное число }

y : integer; { число в вершине дерева }

old : integer; { последнее выведенное число }

inp : text; { входной файл }

out : text; { выходной файл }

bf : boolean; { признак начала вывода последовательности }

bx : boolean; { рабочая переменная }

begin

Assign(inp,'STX.INP'); Reset(inp);

Assign(out,'STX.OUT'); Rewrite(out);

InitST; { инициализация сортировки }

bf:=false; { вывод последовательности еще не начат }

while not Eof(inp) do begin

ReadLn(inp,x); { считывание числа из файла }

{ если в дереве есть свободное место - включить в дерево }

if CheckST(y) <= 1 then bx:=InsertST(x)

else { в дереве нет свободного места }

if (bf and (x < old)) or (not bf and (x < y)) then begin

{ вывод содержимого дерева }

while DeleteST(y) do Write(out,y:3,' ');

WriteLn(out);

bf:=false; { начало новой последовательности }

bx:=InsertST(x); { занесение считанного числа в дерево }

end

else begin { продолжение формирования последовательности }

if x < y then begin { вывод считанного числа }

Write(out,x:3,' '); old:=x;

end;

else begin { вывод числа из вершины дерева }

bx:=DeleteST(y);

Write(out,y:3,' '); old:=y;

{ занесение считанного в дерево }

bx:=InsertST(x);

end;

bf:=true; { вывод последовательности начался }

end;

end;

Close(inp);

{ вывод остатка }

while DeleteST(y) do Write(out,y:3,' ');

WriteLn(out); Close(out);

end.