Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 117
Текст из файла (страница 117)
Фибоначчиевы пирамиды В строках 1-3 алгоритм объединяет списки корней Н1 и Нг в новый список юрней Н. Строки 2, 4 и 5 определяют минимальный узел Н, а в строке б выполняется присвоение и [Н) общего количества узлов фибоначчиевой пирамиды. В строке 7 выполняется освобождение исходных фибоначчиевых пирамид Н1 и Нг, а в строке 8 — возврат получившейся в результате слияния фибоначчиевой пирамиды Н.
Как и в случае процедуры Р1в НеАР 114зект, никакое объединение деревьев не выполняется. Изменение потенциала равно ф (Н) — (а (Н ) + ф(Н )) = = (1 (Н) + 2т (Н)) — ((г (Н|) + 2т (Н1)) + (1(Нг) + 2т (Нг))) = =О, поскольку 1(Н) = 1(Н1) + 1(Нг) и т (Н) = т (Н1) + т (Нг). Амортизированная стоимость процедуры Р1в НеАР 17н1О1ч, таким образом, равна фактической стоимости О (1). Извлечение минимального узла Процесс извлечения минимального узла наиболее сложный из всех операций, рассматриваемых в данном разделе. Это также то место, где выполняются отложенные действия по объединению деревьев. Псевдокод процедуры извлечения минимального узла приведен ниже.
Для удобства предполагается, что когда узел удаляется из связанного списка, указатели, остающиеся в списке, обновляются, но указатели в извлекаемом узле остаются неизменными. В этой процедуре используется вспомогательная процедура СО1чзоь1плте, которая будет представлена чуть позже. Р1В НеАР ЕхткАст Мпч(Н) 1 г — тгп[Н] 2 Няф1ЧП. 3 гйеп 1ог (для) каждого дочернего по отношению к г узла х 4 йо Добавить х в список юрней Н 5 р[х) — 1чп. 6 Удалить з из списка корней Н 7 Н я = ггуьФ] 8 1Ьеп тт[Н] — 1чп. 9 ене т1п[Н) — г19Ы[я] 10 С01чв01дОАте(Н) 11 п[Н) — п[Н) — 1 12 ге1пгп г Часть Ч. Сложные структуры данных »»»»»» (л» ~»»»»(7»»» ф (52Л5 ф ® б) (231- 7) ®.ф.С52) (35».))7) . --~4~) 0 ! 2 б ) 2 ы 23»» 7 '.2),» 4»Я »52''33:» П .
. 24» Ф 14) )»33)) Ф '.46 ;35) ®,7~~2)).ф~52)»3$'(7) —. ~241 ® 0) 21 8 ( л(»(,', 1»; 3» '23)» 7) Й)) ©,52)»35''П'. (24) ,35) '3'.) Рис. 20.3. Работа процедуры Р)в Нвлт Ехтклст М(н Как показано на рис. 20.3, процедура Р)в Ннлв Ехтклст М()4 сначала перемещает в список корней все дочерние узлы минимального узла, а затем удаляет последний из списка корней.
Затем выполняется уплотнение списка корней путем связывания корней одинаковой степени, пока в списке останется не больше одного корня каждой степени. Работа начинается в строке 1, где в переменной з сохраняется указатель иа минимальный узел фибоначчиевой пирамиды — именно этот указатель процедура вернет в конце работы.
Если з = )ч(2., это означает, что фибоначчиева пирамида пуста, и работа на этом заканчивается. В противном случае, как и в процедуре В04ом(ль Нллр Ехтклст Мпч, мы удаляем узел з из Н, делая все дочерние узлы узла з корнями в Н в строках 3-5, помещая их в список корней, и вынося ю него з в строке б. Если после выполнения строки б г = тэдом [з], значит, з был единственным узлом в списке корней, и у него нет дочерних узлов. В этом случае нам остается только сделать фибоначчиеву пирамиду пустой, перед тем как вернуть з в строке 8. В противном случае мы устанавливаем указатель лип [Н) на узел, отличный от з (в нашем случае это тздЫ [я1), причем это не обязательно минимальный узел.
На рис. 20.3б показано состояние исходной фибоначчиевой пирамиды, приведенной на рис. 20.3а, после выполнения строки 9. Следующий этап, на котором будет уменьшено количество деревьев в фибоначчиевой пирамиде, — уплотнение (сопзо1141а21пй) списка корней Н, которое Глава 20. Фибоначчиевы пирамиды 567 0 ! 2 А [71/[А43 0 1 г А Гхх7х'7Л7~~ -- ф» ф Г~~~ 7;07 а4Ю 23;7 Е 63 Ф'.3® ® к7 7 7~-.
"- ®-ф ~32~ (33~. ---. 24 66 40 © Ю «В [307 Р- О ! 2 3 А [А ЦЫЦ] А Ц'Я/~~1 х„х ~- "фф® ® ® Ф ® 7 7 в,к ф ..52,--,Р ~ 2~4,~ ~~~~~ ~23 ' ~,41] ф46 ® Сзф 0~23 выполняется вспомогательной процедурой Со74зо7.773Ати(Н). Уплотнение списка корней состоит в многократном выполнении следующих шагов, до тех пор, пока все корни в списке корней не будут иметь различные значения поля 77еугее. 1. Найти в списке корней два корня х и р с одинаковой степенью, где 70ер [х] < < 70еу [у]. 2. Привязать Ппй) у к х: удалить у из списка корней и сделать его дочерним узлом х.
Эта операция выполняется процедурой г гв Нала 1.пкк. Поле сергее [х] при этом увеличивается, а пометка у, если таковая была, снимается. А Е-~~- х7 577 [. -. - . --..~367 247 077) ®~ ~211 ' ~41,7 ~~~0 7 0~30 ~ Й2)в ® ххз 77й ц 41~7хг Д © (7 0'3 ° 0' 23 А ЯЦЦ~ ~ Х, 7 их ®'С77)Б; Я ф 47, 3 [40~ ®3 Я2 ~ 568 Часть Ч.
Сложные структуры данных Процедура СонзоиоАте использует вспомогательный массив А [0..$3 (п [Н])). Если А [$] = у, то у в настояший момент является корнем со степенью Недгее [у] = СОИБ0$.1оАте(Н) 1 $ог г' — О $о Р(п[Н]) 2 йо А[$) — н1 3 $ог (для) каждого узла зл в списке юрней Н 4 $$ох — ю 5 с1 — Иедтее [х] 6 «Ьйе Аф ~ нп. 7 $$о у — А[И] 1> Узел с той же степенью, что и у х. 8 И' Йеу[х] ) Йеу[у) 9 $Ьеп обменять х ь у 1О Р!В НЕАР $.ПЧК(Н, у, х) 11 А[И] +- нп. 12 д — 0+1 13 А[И] +- х 14 пип[Н] +- Хц. 15 $ог1+- О $о В(п[Н]) 16 Йо 1$' А[$] ~ 1чп. 17 $Ьеп Добавить А[а] в список корней Н 18 1$' тзп[Н] = ни. или йеу[А[г]] ( йеу[тгп[Н]] 19 $Ьеп т$п[Н] +- А[1] Р1В НЕАР $.1ХК(Н, у, х) 1 Удалить у из списка корней Н 2 Сделать у дочерним узлом х, увеличить Иедгее[х) тога[у] — РАЕЗЕ Рассмотрим процедуру СОНЗОЕ1ОАТЕ более подробно.
В строках 1-2 выполняется инициализация А путем присвоения каждому элементу массива значения н1$.. Цикл $ог в строках 3-13 обрабатывает каждый корень зл в списке корней. Обработка каждого корня приводит к созданию дерева, корнем которого является некоторый узел х, юторый может как совпадать, так и не совпадать с ш. После этого ни один корень с списке корней не имеет ту же степень, что и х, так что мы можем присвоить элементу массива А [Ыедгее[х)] значение х.
По завершении работы цикла $ог в списке корней останется не более чем по одному корню каждой степени, и элементы массива А будут указывать на каждый из оставшихся в списке корней. Цикл «Ьйе в строках 6 †связывает корень х дерева, в котором содержится узел ш, с другим деревом, юрень которого имеет ту же степень, что и х. Это Глава 20. Фибоначчиевы пирамиды 569 действие повторяется до тех пор, пока ни один другой корень не будет иметь ту же степень, что и х.
Инвариант цикла згяйе следующий: В начале каждой итерации цикла згЫ!е И = Иедгее[х]. Воспользуемся этим инвариантом цикла для доказательства корректности алго- ритма. Инициализация: строка 5 гарантирует, что инвариант цикла выполняется при входе в цикл. Сохранение: в каждой итерации цикла яЫ1е А [д] указывает на некоторый корень у. Поскольку Н = Ыедгее [х] = Недгее [у], мы хотим связать х и у.
В результате связывания тот из корней, значение ключа которого меньше, становится родительским узлом для другого, так что в строках 8-9 при необходимости выполняется обмен х и у. Затем мы привязываем у к х вызовом процедуры Рш Нплр Ьпчк(Н,у,х) в строке 1О. Этот вызов увеличивает значение Иедгее [х], но оставляет равным Н значение Ыедгее [у]. Поскольку узел у больше не является корнем, указатель на него удаляется из массива А в строке 11. Поскольку вызов процедуры рш Нплр Ь|нк увеличивает значение Иедгее [х], в строке 12 происходит восстановление инварианта Н = Иедгее [х]. Завершение: мы повторяем цикл яЫ1е до тех пор, пока не получим А [д] = ий., так что ни один другой корень не имеет ту же степень, что и х. После завершения цикла згЫ!е мы присваиваем Аф значение х в строке 13 и выполняем очередную итерацию цикла 1ог.
На рис. 20.3е-д показан массив А и деревья, которые получаются в результате первых трех итераций цикла 1ог в строках 3-13. В следующей итерации цикла 1ог выполняется три связывания; их результаты можно увидеть на рис. 20.3е — з. На рис. 20.3и-м представлены результаты следующих четырех итераций цикла 1ог. Теперь все, что остается, — выполнить завершающие действия.
После того как закончена работа цикла в строках 3-13, строка 14 создает пустой список, который заполняется в строках 15-19 на основе данных из массива А. Получившаяся в результате фибоначчиева пирамида показана на рис. 20.3н. После уплотнения списка корней процедура рш Нплп Ехтклст Мпч завершается уменьшением и [Н] в строке 11 и возвратом указателя на удаленный узел г в строке 12.
Заметим, что если перед выполнением процедуры Рш Нплр Ехтклст Мш все деревья в фибоначчиевой пирамиде были неупорядоченными биномиальными деревьями, то и после выполнения процедуры они останутся неупорядоченными биномиальными деревьями. Имеется два пути изменения деревьев. Во-первых, встроках 3-5 процедуры рш Нила Ехтклст Мпч каждый дочерний узел х корня Часть Ч. Сложные структуры данных 570 з становится корнем. В соответствии с упражнением 20.2-2, каждое новое дерево является неупорядоченным биномиальным деревом. Во-вторых, деревья объединяются процедурой РШ НПАВ 1.!МК, только если у них одинаковые степени.
Поскольку все деревья перед связыванием представляют собой неупорядоченные биномиальные деревья, два дерева с корнями, которые имеют по й дочерних узла, должны иметь структуру Уь. Следовательно, получающееся в результате дерево должно иметь структуру Уь+г. Теперь мы готовы показать, что амортизированная стоимость извлечения минимального узла из фибоначчиевой пирамиды с п узлами равна О (.Р (и)). Обозначим через Н фибоначчиеву пирамиду непосредственно перед выполнением операции р~в НпАв ЕхткАст Мпч Фактическую стоимость извлечения минимального узла можно подсчитать следующим образом. Вклад О (Р (и) ) вносит обработка не более Р (и) дочерних узлов минимального узла в процедуре Р[в НеАР Ехтклст Мпч, а также операции в строках 1-2 и 14-19 процедуры СгхчзоиоАтп.
Остается проанализировать вклад цикла 1ог в строках 3-13. Размер списка корней при вызове процедуры СОХЮЫВАтк не превышает Р (и) +1(Н) — 1, поскольку он состоит из исходного списка корней с г(Н) узлами, минус извлеченный узел и плюс дочерние узлы извлеченного узла, количество которых не превышает Р (и). Всякий раз при выполнении цикла зчЫ1е в строках 6-12 один из корней связывается с другим, так что общее количество работы, выполняемой в цикле 1ог, не более чем пропорционально Р (и) + 1 (Н).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
