Cтраница 2
Каким образом объединяются две биномиальных очереди. Прежде всего, следует отметить, что эта операция тривиальна, если обе очереди не содержат сортирующих деревьев степени 2 одинакового размера, как показано на рис. 9.19; мы просто выполняем слияние деревьев из обеих биномиальных очередей и получаем одну биномиальную очередь. [16]
Процесс вставки нового элемента в биномиальную очередь в точности отображает процесс увеличения значения двоичного числа на единицу. Чтобы увеличить значения двоичного числа на единицу, мы двигаемся справа налево, заменяя 1 на 0 в силу необходимости выполнения переноса, обусловленного тем, что 1 1 102, пока не обнаружим 0 в самой правой позиции, который заменяем единицей. Аналогичным образом, чтобы добавить в биномиальную очередь новый элемент, мы продвигаемся справа налево, выполняя слияние сортирующих деревьев, соответствующих битам 1 с переносимым сортирующим деревом, пока не найдем самую правую пустую позицию, в которую и помещаем переносимое дерево. [17]
Другие операции, выполняющиеся в биномиальных очередях, понять проще, если сравнить их с операциями двоичной арифметики. Как мы вскоре убедимся, реализация операции объединить соответствует реализации операции сложения двоичных чисел. [18]
В том случае, когда две объединяемые биномиальные очереди содержат только сортирующие деревья степени 2, размеры которых попарно различны, операция объединения есть ни что иное как слияние. [19]
Добавление биномиальной очереди из 3 узлов к биномиальной очереди из 7узлов имеет своим результатом очередь из 10 узлов как результат выполнения процесса, который моделирует операцию сложения 0112 111210102 двоичной арифметики. Последующее сложение трех 2-деревьев оставляет одно из них в итоговой очереди, а в перенос попадает 4-дерево, содержащее узлы TNEI. Это 4-дерево складывается с другим 4-деревом, образуя биномиальную очередь, показанную в нижней части диаграммы. Процесс охватывает небольшое количество узлов. [20]
Используя соглашения из упражнения 9.1, построить последовательность биномиальных очередей, полученных в результате того, что операции PRIO R I T Y QUE U E выполняются на первоначально пустой биномиальной очереди. [21]
В частности, для вставки нового элемента в биномиальную очередь мы превращаем новый элемент в 1-узловое сортирующее дерево. Далее, если N есть четное число ( значение самого правого разряда равно 0), мы просто помещаем это сортирующее дерево в самую правую пустую позицию биномиальной очереди. Если N - нечетное число ( значение самого правого разряда составляет 1), мы объединяем сортирующее 1-дерево, соответствующее новому элементу, с сортирующим 1-деревом в самой крайней правой позиции биномиальной очереди, в результате чего получаем сортирующее 2-дерево переноса. Если позиция, соответствующая 2 в биномиальной очереди, пуста, то сортирующее дерево переноса помещается в эту позицию, в противном случае производится слияние сортирующего 2-дерева переноса с сортирующим 2 деревом из биномиальной очереди, образуя при этом 4-дерево переноса, и так продолжая процесс до тех пор, пока не будет достигнута пустая позиция в биномиальной очереди. Этот процесс демонстрируется на рис. 9.17, а в программе 9.14 приведена его реализация. [22]
Затем можно воспользоваться операцией объединить, чтобы объединить биномиальную очередь с остальной частью исходной очереди с целью завершения операции удалить наибольший. [23]
EASY вставляются h первоначально пустую биномиальную очередь, и построить биномиальную очередь, которая иалуштся. [24]
Добавить деструктор, конструктор копирования и перегруженную операцию присваивания в реализации биномиальной очереди ( программы 9.13 - 9.16), приведенные в тексте книги, с целью разработки реализации АТД первого класса из упражнения 9.43. Написать программу-драйвер, которая сможет протестировать полученные интерфейс и реализацию. [25]
Построить биномиальную очередь, которая получится, если ключи EASY вставляются в первоначально пустую биномиальную очередь, и построить биномиальную очередь, которая получится, если вставить ключи QUESTIONS первоначально пустую очередь. Затем выполните операцию удалить наибольший в обеих очередях и представьте результат. И наконец, представьте результат выполнения операции объединить применительно к полученным очередям. [26]
Построить биномиальную очередь, которая получится, если ключи EASY QUESTION вставляются в первоначально пустую биномиальную очередь. [27]
Сначала производится просмотр корневых узлов, чтобы выяснить, какой из них больше, затем из биномиальной очереди удаляется сортирующее дерево степени 2, содержащее наибольший элемент. В завершение при помощи операции объединить выполняется слияние полученной таким путем биномиальной очереди и исходной биномиальной очереди. [28]
Лемма 9.7. Все операции на очереди по приоритетам как на абстрактном типе данных могут быть реализованы на биномиальной очереди таким образом, что для выполнения любой из них на очереди из N элементов требуется O ( gN) шагов. [29]
Построить биномиальную очередь, которая получится, если ключи EASY вставляются в первоначально пустую биномиальную очередь, и построить биномиальную очередь, которая получится, если вставить ключи QUESTIONS первоначально пустую очередь. Затем выполните операцию удалить наибольший в обеих очередях и представьте результат. И наконец, представьте результат выполнения операции объединить применительно к полученным очередям. [30]