36. Реализация частично упорядоченного двоичного дерева двоичной кучей.

Дерево частично упорядоченно, сбалансировано и на самом нижнем уровне все литья «сдвинуты влево». Благодаря этому в качестве представления можно использовать двоичную кучу, а именно массив А, в котором 1-ые n позиций соответствуют n узлам дерева. Ячейка А[1] содержит корень дерева, левый сын A[i], если он существует, находится в ячейке A[2i], а правый A[2i + 1].

Обрат. соотношение имеет вид: если сын находится в A[i], i >1, то его родитель находится в ячейке [i div 2]. При таком заполнении массива узлы дерева заполнятся ячейками с A[1] по A[n] последовательно, уровень за уровнем, а внутри уровня слева на право.

Если объявим когнст. maxsize (максимальное число элементов), processtype (случайная расстановка очереди с приоритетом процессов выполненняемых на ЭВМ)

АТД (очередь с приоритетом) можно объявить так:

type

PRIORITYQUEUE = record

contents: array [1..maxsize] of processtype;

last: integer; // last – курсор используемый в последовательности используемых ячеек массива его текущим состоянием.

end;

Рассмотрим реализацию различных операторов АТД, при этом будем полагать, что в нашем расположении находится P(x) и return( ) возвращает результат работы и прерывает работу вызвавшей ее функции.

procedure MAKENULL (var A: PRIPRITYQUEUE);

begin A.last

procedure INSERT (var A: PRIORITYQOEOE; x: processtype);

var i: integer;

temp: processtype;

begin

if A.last > = maxsize then error (‘очередь пуста’)

else begin

A.contents [A.last]:=x;

i:=A.last;

Далее цикл while перемещает новый элемент x вверх по дереву.

while (i >1) out (p(A.contents [i]) < p(A.contents [i div 2])) do

begin temp:=A.contents [i];

A.contents:=A.contents [i div 2];

A.contents [i div 2]:=temp;

i:= i div 2;

end;

end;

end; //конец INSERT

function DELETEMIN (var A: PRIORITYQUEUE)^precesstype; //ссылка на удаленный более приоритетный элемент

var i, j:integer;

temp: procestype;

minimum:^proccesstype;

begin if A.last = othen error (‘очередь пуста’)

else begin

new (minimum); //создание новой ячейки для хранения типов processtype, адрес этой ячейки передается переменной minimum

minimum^:=A.contents [1]; //во временную ячейку отправляется наиболее приоритетный элемент

A.contents [1]:=A.contents[A.last]; //размещаем в корне элемент из последнего листа

A.last:=A.last-1;

i:=1;

Далее while перемещает элемент, попавший в корень, вниз по дереву, если это необходимо

while i<=(A.last div 2) do begin

В следующем условном операторе узел j будет в одном i с наибольшим приоритетом или, если 2i=A.last будет просто сыном i

if (p(A.contents [2*i]) < p(A.contents [2*i+1])) or (2*i = A.last) then

j:=2*i;

else j:=2*i+1;

В следующем условном операторе существует обмен передвигаемого элемента с его сыном имеющим наибольший приоритет

if (p(A.contents [i]) > (p(A.contents [j]))

begin temp:=A.contents [i];

A.contents [i]:=A.contents [j];

A.contents [j]:=temp;

i:=j;

end

else return (minimum); //перемещение далее невозможно

end;

return (minimum); //элемент добрался до листа

end;

end; // конец DELETEMIN