Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 121
Текст из файла (страница 121)
Если после выполнения строки 6 з является собственным правым братом, значит, з был единственным узлом в списке корней, и у него нет дочерних узлов. В этом случае нам остается только сделать фибоначчиеву пирамиду пустой в строке 8, перед тем как вернуть з. В противном случае мы устанавливаем указатель Н. т(п на корень, отличный от з (в нашем случае это правый брат г), причем это не обязательно минимальный узел по завершении процедуры Р!в-НеАЕ-ЕхткАст-М1!ч.
На рис. 19.4,(б) показано состояние исходной фибоначчиевой пирамиды, приведенной на рис. 19.4, (а), после выполнения строки 9. Следующий этап, на котором будет уменьшено количество деревьев в фибоначчиевой пирамиде, — уплотнение (сопзо!1бабп8) списка корней Н, которое выполняется вспомогательной процедурой Сслчзоь!ОАте(Н). Уплотнение списка корней состоит в многократном выполнении следующих шагов до тех пор, пока все корни в списке корней не будут иметь различные значения атрибута Иедтее. !. Найти в списке корней два корня х и у с одинаковой степенью. Пусть, без потери общности, х. )сеу ( у.)сеу.
2. Связать (1!пи) у с х: удалить у из списка корней и сделать его дочерним узлом х. Эта операция выполняется процедурой Г1Е-НеАЕ-Ьпчк. Данная процедура увеличивает атрибут х. с(едтее и снимает пометку с у. 55! Глава 19. Фиааиаччиевы вираииды Процедура СО1чзОЕ111АтЕ использует вспомогательный массив А[0 .. Р(Н.
и)] для отслеживания корней в соответствии с их степенями. Если А[!] = у, то у в настоящий момент является корнем со степенью у. аедгее = !. Конечно, для выделения массива необходимо знать верхнюю границу Р(Н.п) максимальной степени. Как ее вычислить, вы узнаете из раздела 19.4. СОыЯОе!ОАте(Н) ! Пусть А[0 .. Р(Н. и)] — новый массив 2 !ог ! = 0 1о Р(Н. и) 3 А[Г] = 1ч1е 4 Гвг каждый узел ю в списке корней Н 5 х=ю 6 е( = х. с1едгее 7 тг!1йе А[А] ~ 1Ч1Е 8 у = А[е(] // Другой узел с той же степенью, что и у х 9 !Гх.йеу > у.йеу 10 Обменять х и у 11 Р1В-НеАР-ЬВчк(Н, у, х) 12 Аф = м1е 13 0=0+1 14 А[е(] = х 15 Н.тги = 1Ч1Е 16 Гог г' = 0 Го Р(Н. и) 17 !Г А[!] ф 191е 18 !Г Н. т!и == Х1Е 19 Создать список корней Н, содержащий только А[!] 20 Н.т!п = А[!] 21 е1ае Вставить А[!] в список корней Н 22 !ГА[!].1ееу ( Н.тт.йеу 23 Н, тт = А[!] Р!В-НЕАР-Ь!ХК(Н, у, х) 1 Удалить у из списка корней Н 2 Сделать у дочерним узлом х, увеличивая х.
Гедгее 3 у.тату = РАЕЗЕ Рассмотрим процедуру СО1чзое1ОАте более подробно. В строках 1-3 выполняется инициализация массива А путем присвоения каждому элементу массива значения 191 е. Цикл Гвг в строках 4 — 14 обрабатывает каждый корень ю из списка корней. При связывании корней ю может оказаться связанным с некоторым другим узлом и перестать быть корнем. Тем не менее ш всегда находится в дереве, корнем которого является некоторый узел х, который может как совпадать, так и не совпадать с ю. Поскольку мы хотим иметь не более одного корня для каждой степени, мы просматриваем массив А, чтобы узнать, не содержит ли он корень у с той же степенью„что и у х.
Если это так, то мы связываем корни х и у, но Часть К Сложные струклоры далиыг 552 Н,глю (щ ®(~~(215 ф®файф (йб) зь м,й ф яь (ф, ''а., "7')(21) -'2-) ((7) ~Й,. ффаЪВ ф~ ф (4(г © (4() ф~ о~аз е~гй е~зз с~аз А Я-,.(ДР) ( ) "'~17,':: -(21'. ф(52) (~:. (24) ф! ф,. ©:$ ф бб) гбч ф Рис. 19.4. Работа процедуры рзн-Нняг-Еитняст-Мги.
(а) Фибоначчиева пирамида Н. (6) Ситуация после удалении минимального узла л из списка корней и добавления в список его дочерних узлов. (в)-(д) Массив А и деревья после кюкдой из трех итераций цикла уог в строках 4-14 процедуры Сомзоиплтн. Процедура обрабатывает список корней начиная с узла, на который указывает Н. щ(п, и следуя указателям г(длг. В кюкдой части показаны значения ю и к в конце итерации. (е)-(э) Следующая итерация цикла уог с указанием значений ю н ж в конце кюкдой итерации цикла мййе в строках 7-13.
В части (е) показана ситуация после первого правда цикла мййе. Узел с юпочом 23 мазан с узлом с ключом 7, на который в этот момент указывает х. В части (ж) узел с ключом 17 был связан с узлом с ключом 7, на который все еще указывает ж. В части (з) узел с юпочом 24 был связан с узлом с ключом 7. Посюльку ранее А(З) не укажваз ни на один узел, в конце итерации никла уог значение А 13) устанавянваетса указывающим на корень полученного в результате дерева. (в) ф.(7;;.ф ф фф (Зйз (~~1 .
(24( ф (4(;, Уф ф 4)~' е~зз А г; 'эз))газ) Рй (йо (~, а~, ф 192г «%) Г((7)::Й 141) (Зб,:,(б) А( з'~'.~1~) ью г 1„1 (25) ('Ф~ ф() ф 52) (Зф ®. ф 4г()(" ф Ф) (й,.: 0123 А Д, ~Л'тзД (~1 (7".. (2'чз ф.фйз (зб) (77) . Ъ. ф': © '4)) ф~ ~) ~м".
л Я~Я';1 ф ";.~з фф ® Глава ! 9. Фябоиоч чвеаы лираииды О ! 2 3 А ';((!*!Р)ц ( о(гз А (,~э ...' (;* и) ',':7:~ .:,''11',~ ф фЛ',: (Зй) (йа;:: ~~7з) '.23 © (4),; ф:,'4() =а) 0 ! 2 3 А ~уф,"!(9(~~ о(гз А Я. (~~~,~ ) т(,. (я, ! ф:"Й):э()):,3й) (я) (т(1 ф; (З(э),7э, © ('(й) (зв) .'эз) (а) ()' '*,, (Э4! ~~7) 'З'., ф;.44) у~) ф (й)1,! © (41) -,'Й Рис. 19Л (продимкенне). (н)-(м) Ситуапзо! после выполненил каждой ю следуизщнх четырех итерапий пикав Гег. (я) Фибоначчиева пирамкаа Н после восстановления списка корней из массива А и определения нового указателя Н, яз(о. В начале каждой итерации цикла тч(гйе (( = х. ((ертее. Воспользуемся этим инвариантом цикла для доказательства корректности алго- ритма. гарантируем, что после этого х останется корнем. Иначе говоря, мы связываем у с х после первого обмена указателей на эти (юрии, если ключ у меньше ключа х.
После связывания р с х степень х увеличивается на 1, так что мы продолжаем процесс, связывая х и другой корень, степень которого равна новой степени х, и так до тех пор, пока больше не будет корней с той же степенью, что и у х. Затем соответствующий элемент массива А делается указывающим на х, так что при последующей обработке корней у нас уже булет записано, что х является единственным корнем с данной степенью, который уже обработан. По завершении работы цикла (ог в списке корней останется не более чем по одному мэрию каждой степени, и элементы массива А будут указывать на кюкдый из оставшихся в списке корней. Цикл зчЬйе в строках 7-13 связывает корень х дерева, в котором содержится узел ю, с другим деревом, корень каторого имеет ту же степень, что и х. Это действие повторяется до тех пор, пока ни один другой корень не будет иметь ту же степень, что и х.
Инвариант цикла тч()йе следующий: 554 Часть и Схаксные структуры данных Инициализация. Строка 6 гарантирует, что инвариант цикла выполняется при первом входе в цикл. Сохранение. В каждой итерации цикла иЬИе А(е() указывает на некоторый корень у. Поскольку И = х. Иедтее = у. Иедгее, мы хотим связать х и у. В результате операции связывания тот из узлов х и у, который имеет меньший ключ, становится родителем другого, так что в строках 9 и 10 при необходимости выполняется обмен указателей на х и у.
Затем мы связываем у с х вызовом Г!Е-НЕАР-Ьвчк(Н,у,х) в строке 11. Этот вызов увеличивает х. Иедгее, но оставляет у. дедгее равным ь(. Узел у больше не является корнем, так что в строке 12 указатель на него удаляется из массива А. Поскольку вызов Г!в- НЕАР-Ь!Р!К увеличивает значение х. Иедгее, строка 13 восстанавливает инвариант И = х. Иедгее.
Завершение. Цикл згЬИе повторяется до тех пор, пока не будет выполнено условие А(с() = !ч!е, т.е, пока не будет другого корня с той же степенью, что и у х. После завершения цикла хгЬИе мы присваиваем элементу А[с(] значение х в строке 14 и выполняем очередную итерацию цикла гог. На рис. 19.4,(в)-(д) показаны массив А и деревья, которые получаются в результате первых трех итераций цикла гог в строках 4 — 14. В следующей итерации цикла 1ог выполняются три связывания; их результаты можно увидеть на рис.
19.4, (е)-(з). На рис. 19.4, (и)-(м) представлены результаты следующих четырех итераций цикла 1ог. Теперь все, что остается, — выполнить завершающие действия. После того как закончена работа цикла в строках 4-14, строка 15 создает пустой список, который заполняется в строках 16-23 на основе данных из массива А. Полученная в результате фибоначчиева пирамида показана на рис. 19.4,(н). После уплотнения списка корней процедура Г!в-НеАР-ЕхткАст-Мпч завершается уменьшением Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
