Структуры данных и алгоритмы (1021739), страница 33
Текст из файла (страница 33)
Хеш-таблицы следует исключить, поскольку они не имеют подходящего механизма нахождения минимальногоэлемента. Попросту говоря, применение хеширования привносит дополнительныесложности, которых лишены, например, связанные списки.При использовании связанных списков можно выбрать вид упорядочивания элементов списка или оставить его несортированным. Если список отсортирован, то нахождение минимального элемента просто — это первый элемент списка. Но вместе стем вставка нового элемента в отсортированный список требует просмотра в среднем-'.'.•• :.;•••..4.11. РЕАЛИЗАЦИЯ ОЧЕРЕДЕЙ С ПРИОРИТЕТАМИ••.••.:•;••;:...:i,<,• ' 'ft'131половины элементов списка.
Если оставить список неупорядоченным, упрощаетсявставка нового элемента и затрудняется поиск минимального элемента.Пример 4.10. В листинге 4.12 показана реализация функции DELETEMIN длянесортированного списка элементов, имеющих тип processtype, описанный впримере 4.9. В этом листинге также приведены объявления для типа ячеек списка и для АТД PRIORITYQUEUE (Очередь с приоритетами). Реализация операторов INSERT и MAKENULL (как для отсортированных, так и для несортированных списков) не вызывает затруднений, и мы оставляем ее в качестве упражнения для читателей. ПЛистинг 4.12. Реализация очереди с приоритетами посредством связанного спискаtypecelltype = recordelement: processtype;next: tcelltypeend;PRIORITYQUEUE = Tcelltype;{ ячейка указывает на заголовок списка }function DELETEMIN ( var A: PRIORITYQUEUE ): Tcelltype;varcurrent: Tcelltype;{ указывает на ячейку, которая будетпроверена следующей }Jowpriority: integer;{ содержит ранее найденный наименьший приоритет }prewinner: Tcelltype;{ указывает на ячейку, содержащую элементс наименьшим приоритетом }beginif AT.next = nil thenerror('Нельзя найти минимум в пустом списке')else beginlowpriority:= p(AT.nextT.element);{ функция p возвращает приоритет первого элемента.Отметим, что Л указывает на ячейку заголовка,которая не содержит элемента }prewinner:= A;current:= At.next;while currentT.next <> nil do begin{ сравнение текущего наименьшего приоритета сприоритетом следующего элемента }if ptcurrentT.nextT.element)<lowpriority then beginprewinner:= current;lowpriority:= p (сиггел tT.nextT.element)end;сиггел t:= curren tT.nextend;DELETEMIN:= ргеьаплегТ.next;{ возвращает указатель на найденный элемент }prewifinerT.next:= prewinnert.nextT.next...{ удаляет найденный элемент из списка }endend; { DELETEMIN }132ГЛАВА 4.
ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВРеализация очереди с приоритетами посредством частичноупорядоченных деревьевКакие бы мы ни выбрали списки, упорядоченные или нет, для представленияочередей с приоритетами придется затратить время, пропорциональное п, для выполнения операторов INSERT и DELETEMIN на множестве размера п. Существуетдругая реализация очередей с приоритетами, в которой на выполнение этих операторов требуется порядка O(logn) шагов, что значительно меньше п для больших п(скажем, для п > 100). Основная идея такой реализации заключается в том, чтобыорганизовать элементы очереди в виде сбалансированного1 (по возможности) двоичного дерева (рис. 4.6). На нижнем уровне, где некоторые листья могут отсутствовать,мы требуем, чтобы все отсутствующие листья в принципе могли располагаться только справа от присутствующих листьев нижнего уровня.Более существенно, что дерево частично упорядочено.
Это означает, что приоритет узла v не больше приоритета любого сына узла v, где приоритет узла — это значение приоритета элемента, хранящегося в данном узле. Из рис. 4.6 видно, что малые значения приоритетов не могут появиться на более высоком уровне, где естьбольшие значения приоритетов.
Например, на третьем уровне располагаются приоритеты 6 и 8, которые меньше приоритета 9, расположенного на втором уровне. Но родитель узлов с приоритетами 6 и 8, расположенный на втором уровне, имеет (и должен иметь) по крайней мере не больший приоритет, чем его сыновья.10189Рис, 4.6. Частично упорядоченное деревоПри выполнении функции DELETEMIN возвращается элемент с минимальнымприоритетом, который, очевидно; должен быть корнем дерева.
Но если мы простоудалим корень, то тем самым разрушим дерево. Чтобы не разрушить дерево и сохранить частичную упорядоченность значений приоритетов на дереве после удалениякорня, мы делаем следующее: сначала находим на самом нижнем уровне самый правый узел и временно помещаем его в корень дерева. На рис. 4.7,а показаны изменения, сделанные на дереве рис. 4.6 после удаления корня. Затем этот элемент мыспускаем по ветвям дерева вниз (на более низкие уровни), по пути меняя его местамис сыновьями, имеющими меньший приоритет, до тех пор, пока этот элемент не станет листом или не встанет в позицию, где его сыновья будут иметь по крайней мерене меньший приоритет.На рис.
4.7,а надо поменять местами корень и его сына, имеющего меньший приоритет, равный 5. Результат показан на рис. 4.7,6. Наш элемент надо спустить еще1Сбалансированность в данном случае конструктивно можно определить так: листья возможны только на самом нижнем уровне или на предыдущем, но не на более высоких уровнях.Другими словами, максимально возможная сбалансированность двоичного дерева здесь понимается в том смысле, чтобы дерево было как можно "ближе" к полному двоичному дереву. Отметим также, что это понятие сбалансированности дерева не следует путать с асбалансированностью деревьев и подобными характеристиками, хотя они и находятся в определенном "родстве".
— Прим. ред.4.11. РЕАЛИЗАЦИЯ ОЧЕРЕДЕЙ С ПРИОРИТЕТАМИ133на' более низкий уровень, так как его сыновья сейчас имеют приоритеты 6 и 8. Меняем его местами с сыном, имеющим наименьший приоритет 6. Полученное в результате такого обмена новое дерево показано на рис. 4.7,в. Это дерево уже являетсячастично упорядоченным и его дальше не надо менять.Рис. 4.7. Спуск элемента по деревуЕсли при таком преобразовании узел v содержит элемент с приоритетом а и егосыновьями являются элементы с приоритетами Ъ и с, из которых хотя бы одинменьше а, то меняются местами элемент с приоритетом а и элемент с наименьшимприоритетом из & и с.
В результате в узле v будет находиться элемент с приоритетом,не превышающим приоритеты своих сыновей. Чтобы доказать это, для определенности положим, что Ь <: с. После обмена элементами узел v будет содержать элемент сприоритетом Ь, а его сыновья — элементы с приоритетами а и с. Мы предположили,что Ь < с и а не меньше, по крайней мере, или Ь, или с. Отсюда следует Ь < а, что итребовалось доказать. Таким образом, описанный процесс спуска элемента по деревуприводит к частичному упорядочиванию двоичного дерева.Теперь покажем, что оператор DELETEMIN, выполняемый над множеством из пэлементов, требует времени порядка O(logn).
Это следует из того факта, что в деревенет пути, состоящего из больше чем 1 + logn узлов1, а также вследствие того, чтопроцесс прохождения элементом каждого узла занимает постоянное фиксированноевремя. Так как для любой положительной константы с и при п > 2 величинас(1 -I- logn) не превышает 2clogn, то с(1 + logn) имеет порядок O(logn).Теперь рассмотрим, как на частично упорядоченных деревьях работает операторINSERT. Сначала поместим новый элемент в самую левую свободную позицию на самом нижнем уровне, если же этот уровень заполнен, то следует начать новый уро1Здесь подразумевается логарифм по основанию 2. Приведенную оценку можно доказатьисходя из упражнения 3.18 главы 3 или непосредственно методом математической индукциипо п.
— Прим. ред.134ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВвень. На рис. 4.8,а показана вставка элемента с приоритетом 4 в дерево из рис. 4.6.Если новый элемент имеет меньший приоритет, чем у его родителя, то они меняютсяместами. Таким образом, новый элемент теперь находится в позиции, когда у егосыновей больший приоритет, чем у него. Но возможно, что у его нового родителяприоритет больше, чем у него. В этом случае они также меняются местами. Этотпроцесс продолжается до тех пор, пока новый элемент не окажется в корне дереваили не займет позицию, где приоритет родителя не будет превышать приоритет нового элемента.
Рис. 4.8,6, в показывают этапы перемещения нового элемента.91018 941018 9а810Л ЛЛл610.518 99108бРис. 4.8. Вставка нового элементаТеперь докажем, что в результате описанных выше действий получим частичноупорядоченное дерево. Поскольку мы не пытаемся провести строгое доказательство,то просто рассмотрим ситуации, когда элемент с приоритетом а может стать родителем элемента с приоритетом Ь. (Далее для простоты изложения будем отождествлятьэлемент с его приоритетом.)1.Элемент а — это новый элемент, который, перемещаясь по дереву вверх, заменил родителя элемента Ь.
Пусть старый родитель элемента Ь имел приоритет с,тогда а < с, иначе не произошла бы замена. Но с < Ь, поскольку исходное деревочастично упорядочено. Отсюда следует, что а < Ь. Пример такой ситуации показан на рис. 4.8,в, где элемент 4 становится родителем элемента 6, заменяя егородителя с приоритетом 5.2. Элемент а спустился вниз по дереву вследствие обмена с новым элементом. Вэтом случае в исходном дереве элемент а должен быть предком элемента Ь. Поэтому а < Ъ.
На рис. 4.8,в элемент 5, ставший родителем элементов с приоритетами 8 и 9, ранее был их "дедушкой".3. Элемент Ь — новый элемент, который, перемещаясь вверх по дереву, стал сыномэлемента а. Если а > Ь, то на следующем шаге они поменяются местами, ликвидируя тем самым нарушение свойства упорядоченности дерева.Время выполнения оператора вставки пропорционально пути, пройденному новымэлементом. Так же, как и в случае оператора DELETEMIN, этот путь не может бытьбольше 1 -I- logra. Таким образом, время выполнения обоих этих операторов имеет порядок O(logn).Реализация частично упорядоченных деревьев посредством массивовИсходя из того, что рассматриваемые нами деревья являются двоичными, по возможности сбалансированными и на самом нижнем уровне все листья "сдвинуты"влево, можно применить для этих деревьев необычное представление, которое называется куча. В этом представлении используется массив, назовем его А, в которомпервые л позиций соответствуют га узлам дерева.
Д[1] содержит корень дерева. Левыйсын узла .A[i], если он существует, находится в ячейке A[2i], а правый сын, если он4.11. РЕАЛИЗАЦИЯ ОЧЕРЕДЕЙ С ПРИОРИТЕТАМИ135также существует, — в ячейке A[2i + 1]. Обратное преобразование: если сын находится в ячейке A[i], i > 1, то его родитель — в ячейке A[i div 2]. Отсюда видно, чтоузлы дерева заполняют ячейки А[1], А[2], ..., А[п] последовательно уровень за уровнем, начиная с корня, а внутри уровня — слева направо. Например, дерево, показанное на рис. 4.6, будет представлено в массиве следующей последовательностьюсвоих узлов: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.В данном случае мы можем объявить АТД PRIORITYQUEUE (Очередь с приоритетами) как записи с полем contents для массива элементов типа, например processtype, как в примере 4.9, и полем last целочисленного типа, значение которого указывает на последний используемый элемент массива.
Если мы также введем константу maxsize, равную количеству элементов очереди, то получим следующееобъявление типов:typePRIORITYQUEUE = recordcontents: array[1..maxsize] of processtype;last: integerend;Реализация операторов, выполняемых над очередью с приоритетами, показана вследующем листинге.Листинг 4.13. Реализация очереди с приоритетами посредством массиваprocedure MAKENULL ( var Л: PRIORITYQUEUE );beginA.last:= Оend; { MAKENULL }procedure INSERT ( x: processtype; var A: PRIORITYQUEUE ) ,vari: integer;temp: processtype;beginif A.last >= maxsize thenerror!'Очередь заполнена')else beginA.last:= A.last + 1;• A,contents[A.last]:= x;i:= A.last; { i — индекс текущей позиции х }while (i > 1) and (p(A.contents[i]) <p(A.contents[i div 2])) dobegin { перемещение x вверх по дереву путем обменаместами с родителем, имеющим больший приоритет }temp:= A.contents[i] ;Л.contents[i]:= A.contents[i div 2];A.contents[i div 2]:= temp;i:= i div 2endendend; { INSERT }function DELETEMIN ( var A: PRIORITYQUEUE ): Tprocesstype;vari, j: integer;temp: processtype;136ГЛАВА 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
