Биномиальная очередь
Cтраница 3
Если в биномиальной очереди сортирующее 2 -дере & о отсутствует, в рчервдь помещается 2 - дере во переноса, Если а биномиальной очереди такое дерево есть, оно объединяется с таким же новым деревом ( с применением фу кцим pair из программы 9.13) и получается 2 - дере во, после чего значение j увеличивается на 1 и процесс л ро до л кается до так лор. [31]
& нт, Далее из сортирующего дерева степ & ки 2 удаляется корневой узел, содержащий наибольший элвмйкт, и временно строится биномиальная очередь, которая содержит остальные составляющие части сортирующего дерева степени 2 В завершение при помощи операции объединить выполняется сг. [32]
В целях упрощения будем считать, что наши реализации проходят в цикле через все деревья, так что время их выполнения пропорционально логарифму максимального размера биномиальной очереди. [33]
Используя соглашения из упражнения 9.1, построить последовательность биномиальных очередей, полученных в результате того, что операции PRIO R I T Y QUE U E выполняются на первоначально пустой биномиальной очереди. [34]
Определение 9.6. Биномиальная очередь представляет собой набор сортирующих деревьев степени 2, ни одно из которых не совпадает с остальными по размеру. Структура биномиальной очереди определяется числом узлов этой очереди в соответствии с двоичным представлением целых чисел. [35]
Если в биномиальной очереди сортирующее 2 -дерево отсутствует, в очередь помещается 2 -дерево переноса. Если в биномиальной очереди такое дерево есть, оно объединяется с таким же новым деревом ( с применением функции pair из программы 9.13) и получается 2 1-дерево, после чего значение / увеличивается на 1 и процесс продолжается до тех пор, пока не обнаруживается пустая позиция для сортирующего дерева в биномиальной очереди. [36]
Биномиальная очередь размера N представляет собой список левосторонних пирамидально упорядоченных сортирующих деревьев степеней 2, по одному на каждый бит двоичного представления числа N. Таким образом, биномиальная очередь размера 13 - 11012 состоит из одного 8-узлового сортирующего дерева, одного 4-узлового и одного 1-узлового деревьев. На диаграмме показано представление в виде левостороннего пирамидально упорядоченного сортирующего дерева степеней 2 ( сверху) и представление в виде биномиального пирамидально упорядоченного дерева ( внизу) одной и той же биномиальной очереди. [37]
Можно также реализовать операцию удалить наибольший ( remove the maximum) путем одного вызова операции объединить. Для нахождения максимального элемента в биномиальной очереди просматриваются сортирующие деревья степени 2 этой очереди. Каждое такое дерево - левостороннее пирамидально упорядоченное сортирующее дерево, следовательно, максимальный его элемент находится в корне. Больший из корневых элементов является наибольшим элементом биномиальной очереди. [38]
Убрав корень, полунаем бор сортирующих деревьев степени 2; все они левосторонне пирамидально упорядочены, при этом их корни берутся из правого ствола дерева. Эта операция позволяет найти способ удаления наибольшего элемента из биномиальной очереди: убираем корень сортирующего дерева степени 2, которое содержит наибольший элемент, затем выполняем операцию объединить для слияния полученной биномиальной очереди с остальными сортирующими деревьями степени 2 исходной биномиальной очереди. [39]
Сначала производится просмотр корневых узлов, чтобы выяснить, какой из них больше, затем из биномиальной очереди удаляется сортирующее дерево степени 2, содержащее наибольший элемент. В завершение при помощи операции объединить выполняется слияние полученной таким путем биномиальной очереди и исходной биномиальной очереди. [40]
Сначала производится просмотр корневых узлов, чтобы выяснить, какой из них больше, затем из биномиальной очереди удаляется сортирующее дерево степени 2, содержащее наибольший элемент. В завершение при помощи операции объединить выполняется слияние полученной таким путем биномиальной очереди и исходной биномиальной очереди. [41]
Соответствующая программа ненамного сложнее, чем программа простого арифметического сложения, поскольку в этом случае мы имеем дело с четко различимыми сортирующими деревьями, а не с неразличимыми битами, однако в обоих случаях принципиальных трудностей не возникает. Например, если все три разряда принимают значения 1, мы должны оставить одно дерево в получающейся биномиальной очереди, а два других объединить и перенести в следующую позицию. [42]
Чтобы объединить два сортирующих дерева степени 2 одинаковых размеров в одно сортирующее дерево степени 2 двойного размера достаточно изменить лишь несколько связей. Эта функция, которая в реализации определена как приватная функция-член, представляет собой ключевой фактор, обеспечивающий эффективность алгоритма биномиальной очереди. [43]
Указанные рамки производительности служат целью разработки соответствующей структуры данных. Они представляют собой последствия того факта, что во всех реализациях имеется один или два цикла, которые выполняют итерацию на корнях деревьев биномиальной очереди. [44]
 |
Стоимость операций, поддерживающих очередь по приоритетам, для наихудшего случая. [45] |
Страницы: 1 2 3 4