Cтраница 4
При разработке завершенной реализации необходимо соблюдать все интерфейсные требования - в особенности то, как клиентские программы осуществляют доступ к узлам при выполнения операций удалить и изменить приоритет, и как они осуществляют доступ к самим очередям по приоритетам как к типам данных при выполнении операции объединить. Эти проблемы изучаются разделах 9.4 и 9.7, в которых рассматриваются две завершенных реализации: в одной реализации используются двухсвязные неупорядоченные списки, а в другой - биномиальные очереди. [46]
В частности, для вставки нового элемента в биномиальную очередь мы превращаем новый элемент в 1-узловое сортирующее дерево. Далее, если N есть четное число ( значение самого правого разряда равно 0), мы просто помещаем это сортирующее дерево в самую правую пустую позицию биномиальной очереди. Если N - нечетное число ( значение самого правого разряда составляет 1), мы объединяем сортирующее 1-дерево, соответствующее новому элементу, с сортирующим 1-деревом в самой крайней правой позиции биномиальной очереди, в результате чего получаем сортирующее 2-дерево переноса. Если позиция, соответствующая 2 в биномиальной очереди, пуста, то сортирующее дерево переноса помещается в эту позицию, в противном случае производится слияние сортирующего 2-дерева переноса с сортирующим 2 деревом из биномиальной очереди, образуя при этом 4-дерево переноса, и так продолжая процесс до тех пор, пока не будет достигнута пустая позиция в биномиальной очереди. Этот процесс демонстрируется на рис. 9.17, а в программе 9.14 приведена его реализация. [47]
Убрав корень, полунаем бор сортирующих деревьев степени 2; все они левосторонне пирамидально упорядочены, при этом их корни берутся из правого ствола дерева. Эта операция позволяет найти способ удаления наибольшего элемента из биномиальной очереди: убираем корень сортирующего дерева степени 2, которое содержит наибольший элемент, затем выполняем операцию объединить для слияния полученной биномиальной очереди с остальными сортирующими деревьями степени 2 исходной биномиальной очереди. [48]
Каким образом объединяются две биномиальных очереди. Прежде всего, следует отметить, что эта операция тривиальна, если обе очереди не содержат сортирующих деревьев степени 2 одинакового размера, как показано на рис. 9.19; мы просто выполняем слияние деревьев из обеих биномиальных очередей и получаем одну биномиальную очередь. [49]
Убрав корень, полунаем бор сортирующих деревьев степени 2; все они левосторонне пирамидально упорядочены, при этом их корни берутся из правого ствола дерева. Эта операция позволяет найти способ удаления наибольшего элемента из биномиальной очереди: убираем корень сортирующего дерева степени 2, которое содержит наибольший элемент, затем выполняем операцию объединить для слияния полученной биномиальной очереди с остальными сортирующими деревьями степени 2 исходной биномиальной очереди. [50]