ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Реализация очереди с приоритетами посредством частично упорядоченных деревьев

Алгоритмы структуры данных

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

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

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

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

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

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

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

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

На рис. 4.8,а показана вставка элемента с приоритетом 4 в дерево из рис. 4.6. Если новый элемент имеет меньший приоритет, чем у его родителя, то они меняются местами. Таким образом, новый элемент теперь находится в позиции, когда у его сыновей больший приоритет, чем у него. Но возможно, что у его нового родителя приоритет больше, чем у него. В этом случае они также меняются местами. Этот процесс продолжается до тех пор, пока новый элемент не окажется в корне дерева или не займет позицию, где приоритет родителя не будет превышать приоритет нового элемента. Рис. 4.8,6, в показывают этапы перемещения нового элемента.

 

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

1.    Элемент а — это новый элемент, который, перемещаясь по дереву вверх, заменил родителя элемента b. Пусть старый родитель элемента b имел приоритет с, тогда а < с, иначе не произошла бы замена. Но с b, поскольку исходное дерево частично упорядочено. Отсюда следует, что а < b. Пример такой ситуации показан на рис. 4.8,в, где элемент 4 становится родителем элемента 6, заменяя его родителя с приоритетом 5.

2.    Элемент а спустился вниз по дереву вследствие обмена с новым элементом. В этом случае в исходном дереве элемент а должен быть предком элемента b. Поэтому а ≤ b. На рис. 4.8,в элемент 5, ставший родителем элементов с приоритетами 8 и 9, ранее был их "дедушкой".

3.    Элемент b — новый элемент, который, перемещаясь вверх по дереву, стал сыном элемента а. Если а > b, то на следующем шаге они поменяются местами, ликвидируя тем самым нарушение свойства упорядоченности дерева.

Время выполнения оператора вставки пропорционально пути, пройденному новым элементом. Так же, как и в случае оператора DELETEMIN, этот путь не может быть больше 1 + log n. Таким образом, время выполнения обоих этих операторов имеет порядок O(log n).

 

 

 

61