Главная Промышленная автоматика.

половины элементов списка. Если оставить список неупорядоченным, упрощается вставка нового элемента и затрудняется поиск минимального элемента.

Пример 4.10. В листинге 4.12 показана реализация функции DELETEMIN для несортированного списка элементов, имеющих тип processtype, описанный в примере 4.9. В этом листинге также приведены объявления для типа ячеек списка и для АТД PRIORITYQUEUE (Очередь с приоритетами). Реализация операторов INSERT и MAKENULL (как для отсортированных, так и для несортированных списков) не вызывает затруднений, и мы оставляем ее в качестве упражнения для читателей. □

Листинг 4.12. Реализация очереди с приоритетами посредством связанного списка type

celltype = record

element: processtype; next: tcelltype

end;

PRIORITYQUEUE = Tcelltype;

{ ячейка указывает на заголовок списка )

function DELETEMIN ( var A: PRIORITYQUEUE ) : Tcelltype; var

current: Tcelltype;

{ указывает на ячейку, которая будет проверена следующей ) Jowpriority: integer;

{ содержит ранее найденный наименьший приоритет ) prewinner: Tcelltype;

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

begin

if At.next = nil then

error(Нельзя найти минимум в пустом списке) else begin

iowpriority:= p(At.nextt.element) ;

{ функция p возвращает приоритет первого элемента. Отметим, что Л указывает на ячейку заголовка, которая не содержит элемента ) prewinner:= А; current: = At. next;

while currentT.next <> nil do begin

{ сравнение текущего наименьшего приоритета с

приоритетом следующего элемента ) if p(cLJrrentt.nextt.element)<loii53riority then begin рге№гллег:= current;

lowpriority: = p (cLJrreлtt.nextt.element)

end;

cиггeлt:= сиггел tt.next

end;

DELETEMIN:= prewiллert.пext;

{ возвращает указатель на найденный элемент ) prewinnerT.next:= prewlnnerT.nextt.next

{ удаляет найденный элемент из сгшска )

end; { DELETEMIN }



Реализация очереди с приоритетами посредством частично упорядоченныхдеревьев

Какие бы мы ни выбрали списки, упорядоченные или нет, для представления очередей с приоритетами придется затратить время, пропорциональное п, для выполнения операторов INSERT и DELETEMIN на множестве размера п. Существует другая реализация очередей с приоритетами, в которой на выполнение этих операторов требуется порядка O(logra) шагов, что значительно меньше п для больших п (скажем, для п > 100). Основная идея такой реализации заключается в том, чтобы организовать элементы очереди в виде сбалансированного (по возможности) двоичного дерева (рис. 4.6). На нижнем уровне, где некоторые листья могут отсутствовать, мы требуем, чтобы все отсутствующие листья в принципе могли располагаться только справа от присутствующих листьев нижнего уровня.

Более существенно, что дерево частично упорядочено. Это означает, что приоритет узла V не больше приоритета любого сына узла v, где приоритет узла - это значение приоритета элемента, хранящегося в данном узле. Из рис. 4.6 видно, что малые значения приоритетов не могут появиться на более высоком уровне, где есть большие значения приоритетов. Например, на третьем уровне располагаются приоритеты 6 и 8, которые меньше приоритета 9, расположенного на втором уровне. Но родитель узлов с приоритетами 6 и 8, расположенный на втором уровне, имеет (и должен иметь) по крайней мере не больший приоритет, чем его сыновья.


10 18 9

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

При выполнении функции DELETEMIN возвращается элемент с минимальным приоритетом, который, очевидно; должен быть корнем дерева. Но если мы просто удалим корень, то тем самым разрушим дерево. Чтобы не разрушить дерево и сохранить частичную упорядоченность значений приоритетов на дереве после удаления корня, мы делаем следующее: сначала находим на самом нижнем уровне самый правый узел и временно помещаем его в корень дерева. На рис. 4.7,а показаны изменения, сделанные на дереве рис. 4.6 после удаления корня. Затем этот элемент мы спускаем по ветвям дерева вниз (на более низкие уровни), по пути меняя его местами с сыновьями, имеющими меньший приоритет, до тех пор, пока этот элемент не станет листом или не встанет в позицию, где его сыновья будут иметь по крайней мере не меньший приоритет.

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

Сбалансированность в данном случае конструктивно можно определить так: листья возможны только на самом нижнем уровне или на предыдущем, но не на более высоких уровнях. Другими словами, максимально возможная сбалансированность двоичного дерева здесь понимается в том смысле, чтобы дерево было как можно "ближе" к полному двоичному дереву. Отметим также, что это понятие сбалансированности дерева не следует путать с а-сбалансированностью деревьев и подобными характеристиками, хотя они и находятся в определенном "родстве". - Прим. ред.



на более низкий уровень, так как его сыновья сейчас имеют приоритеты 6 и 8. Меняем его местами с сыном, имеющим наименьщий приоритет 6. Полученное в результате такого обмена новое дерево показано на рис. 4.7,в. Это дерево уже является частично упорядоченным и его дальще не надо менять.


Рис. 4.7. Спуск элемента по дереву

Если при таком преобразовании узел v содержит элемент с приоритетом а и его сыновьями являются элементы с приоритетами и с, из которых хотя бы один меньще а, то меняются местами элемент с приоритетом а и элемент с наименьщим приоритетом из & и с. В результате в узле v будет находиться элемент с приоритетом, не превыщающим приоритеты своих сыновей. Чтобы доказать это, для определенности положим, что Ь < с. После обмена элементами узел v будет содержать элемент с приоритетом Ь, а его сыновья - элементы с приоритетами а и с. Мы предположили, что Ь < с и а не меньще, по крайней мере, или Ь, или с. Отсюда следует Ь < а, что и требовалось доказать. Таким образом, описанный процесс спуска элемента по дереву приводит к частичному упорядочиванию двоичного дерева.

Теперь покажем, что оператор DELETEMIN, выполняемый над множеством из л элементов, требует времени порядка O(logra). Это следует из того факта, что в дереве нет пути, состоящего из больще чем 1 + logra узлов, а также вследствие того, что процесс прохождения элементом каждого узла занимает постоянное фиксированное время. Так как для любой положительной константы с и при п > 2 величина с(1 -Ь logn) не превыщает 2clogra, то с(1 + log л) имеет порядок O(logra).

Теперь рассмотрим, как на частично упорядоченных деревьях работает оператор INSERT. Сначала поместим новый элемент в самую левую свободную позицию на самом нижнем уровне, если же этот уровень заполнен, то следует начать новый уро-

Здесь подразумевается логарифм по основанию 2. Приведенную оценку можно доказать исходя из упражнения 3.18 главы 3 или непосредственно методом математической индукции по п. - Прим. ред.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 [40] 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002