Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 113
Текст из файла (страница 113)
Поскольку проверить надо не более [1я и] + 1 корней, время работы процедуры В1ыомы. НнАР М1ы1мим составляет 0 (оп). Глава 19. Биномиальные пирамиды Слияние двух биномиальных пирамид Операция по слиянию двух биномиальных пирамид используется в качестве подпрограммы в большинстве остальных операций. Процедура В!ном!Ап НеА!' Умом многократно связывает биномиальные деревья с корнями одинаковой степени.
Приведенная далее процедура связывает дерево Вь ! с корнем у с деревом Вь ! с корнем «, делая «родительским узлом для у, после чего узел «становится корнем дерева Вь.' Впчомы. 1.пчк(у, «) 1 р[у] + — « 2 «1Ызпд[у] + — сЬ1Ы[«] 3 сЬ11а[«] - у 4 Йедтее[«] +- Йеутее[«] + 1 Процедура Впчом!и. 1.!нк делает узел у новым заголовком связанного списка дочерних узлов узла «за время О (1). Работа процедуры основана на том, что представление с левым дочерним и правым сестринским узлами каждого биномиального дерева отвечают свойству упорядоченности дерева: в биномиальном дереве Вь крайний левый дочерний узел корня является корнем биномиального дерева Вь !.
Приведенная далее процедура сливает биномиальные пирамиды Н! и Нз, возвращая получаемую в результате биномиальную пирамиду, причем в процессе слияния представления биномиальных пирамид Н! и Нз уничтожаются. Помимо процедуры Впчом!м. 1.пчк, данная процедура использует вспомогательную процедуру Впчом!Ап НеАР Мекое, которая объединяет списки корней Н! и Нз в единый связанный список, отсортированный по степеням в монотонно возрастающем порядке. Процедура Впчом!Ап НеАР Мекое, написание которой мы оставляем в качестве упражнения 19.2-1, подобна процедуре Мекое из раздела 2.3.1. Впчом!Ап НБАР 13х!ОР!(Нг, Нз) 1 Н +- МАке Вциом!Ап НеАРО 2 ЬеаИ[Н] — Впчом!АП НеАР Мекае(Н!,Нз) 3 Освобождение объектов Н! и Нз, но не списков, на которые они указывают 4 и Ьеай[Н] = гШ. 5 тпеп ге1пгп Н 6 ртес-х — !ч!ь 7 х +- Ьеад[Н] 8 яехт-х — аеЬ1гпд[х] 9 юй1!е пех1-х ф !ч!ь 1О бо и (Йеутее[х] ~ !1еутее[пехвх]) или («161гпд[пехвх] ф нй.
и Иедтее[НЫ1пд[пехт-х]] = аеутее[х]) Часть Ч. Сложные структуры данных Феп с Случаи 1 я1 [> Случаи 1 и 2 11 12 13 е1зе 14 15 16 17 18 19 20 21 пех1-х +- 22 гетцгп Н Ргеи-х +- х х — пех1-х Ы йеу[х] < *кеу[пехе-х] тйеп вебйпд[х] +- в1б(гпд[пехе-х] В1МОМ1АЬ Ь1МК(пвхб-х, х) е1зе !1' ргее-х = ньь Феп беай[Н] — пехт-х е1яе в1б(гпд[ргее»-х] - пех1-х ВПЧОМЬАЬ Ь1МК(х, пех1-х) х +- пех1-х вгб(епд [х] 1> Случай 3 с Случай 3 1> Случай 4 г» Случай 4 с Случай4 с Случай4 с Случай 4 На рис.
19.4 показан пример работы процедуры ВпчОМ1АЬ НКАР 1)н1ом для всех четырех случаев, приведенных в псевдокоде. На рис. 19.4а показаны исходные биномиальные пирамиды Н1 и Нз. Рис. 19.4б иллюстрирует биномиальную пирамиду Н, которая является результатом работы процедуры В1но. м!Аь НеАР Мекбе(Нг, Нз). Изначально х является первым юрием в списке корней Н. Поскольку и х, и пехг-х имеют степень О, и 1ееу [х] ( йеу [пех1-х], реали. зуегся случай 3. После связывания, как видно из рис. 19.4в, х является первым из трех корней с одной и той же степенью, так что реализуется случай 2.
После того как все указатели сдвигаются на одну позицию в списке юрней (рис. 19.4г), реализуется случай 4 (х является первым из двух корней равной степени). После связывания реализуется случай 3 (рис. 19.4д). После очередного связывания степень х становится равной 3, а степень пехе-х — 4, так что реализуется случай 1 (рис. 19.4е). Эта итерация цикла — последняя, поскольку после очередного перемещения указателей пеат-х становится равным М1Ь. Процедура В1ном1Аь НеАР Ыч1Он имеет две фазы. Первая фаза осуществляется вызовом процедуры В!хОм!Аь НеАР Мекбе, объединяет списки корней биномиальных пирамид Н1 и Нз в единый связанный список Н, который отсортировав по степеням юрней в монотонно возрастающем порядке.
Однако в списке может оказаться по два (но не более) корня каждой степени, так что вторая фаза связывает юрии одинаковой степени до тех пор, пока все юрии не будут иметь разную степень. Поскольку связанный список Н отсортирован по степеням, все операции по связыванию выполняются достаточно быстро.
Более подробно процедура работает следующим образом. Процедура начинается с объединения в строках 1-3 списков корней биномиальных пирамид Н1 и Нз в единый список корней Н. Списки юрней Н1 и Нз отсортированы в строго возрастающем порядке; процедура В1мОм1Аь НеАР МекОе возвращает список корней Н, который также отсортирован в строго возрастающем порядке степеней корней.
Если списки корней Н1 и Нз содержат всего тп корней, то время работы 547 Глава 19. Биномиальные пирамиды процедуры В!ыом!Аь Нел!' Мекое составляет О (т). Процедура на каждом шаге сравнивает корни в начале двух списков корней и добавляет в результирующий список корень с меньшей степенью, удаляя его из исходного списка. Затем процедура В!ном!Аь НеАР Уьлоы инициализирует ряд указателей в списке корней Н. В случае, если происходит слияние двух пустых биномиальных пирамид, в строках 4-5 выполняется возврат пустой биномиальной пирамиды.
Начиная со строки б, нам известно, что в биномиальной пирамиде Н имеется по крайней мере один корень. В процедуре поддерживаются три указателя внутрь списка корней. ° х указывает на текущий корень. ° ргев-х указывает на корень, предшествующий х в списке корней: иИгпд [ргее-х) = х. Поскольку изначально х не имеет предшественника, мы начинаем работу со значения ргее-х, равного ьп! .
° пехг-х указывает на корень, следующий в списке корней за х: згб11пд [х) = = пех1-х. Изначально в списке корней Н имеется не более двух узлов с данной степенью: поскольку Н! и Нз были биномиальными пирамидами, каждая из них имела не более одного корня данной степени. Кроме того, процедура В!ном!Аь Нелв Мекое гарантирует, что если два корня в Н имеют одну и ту же степень, то эти корни соседствуют в списке корней. В действительности, в процессе работы Впчом!Аь НеАР 1)яон в некоторый момент в списке корней Н могут оказаться три корня данной степени — вскоре вы увидите, как может реализоваться такая ситуация. При каждой итерации цикла ч~Ь11е в строках 9-21, мы должны решить, следует ли связывать х и пех1-х, учитывая их степени и, возможно, степень ай1гпд [пех1-х). Инвариантом цикла является то, что в начале каждого выполнения тела цикла и х, и пех1-х не равны н! (в упражнении 19.2-4 рассматривается точный инвариант цикла).
Случай 1, показанный на рис. 19.5а, реализуется, когда !1едгее [х] ф ~ аедгее [иех1-х), т.е. когда х является корнем Вь-дерева, а пех1-х — корнем В!-дерева, причем 1 ) й. Эта ситуация обрабатывается в строках 11-12. Мы не связываем х и пех1-х, так что мы просто смещаем указатели на одну позицию по списку. Обновление указателя пехг-х, который указывает на корень, следующий за х, выполняется в строке 21, поскольку это действие — общее для всех случаев.
Случай 2 (рис. 19.56) реализуется, когда х является первым из трех корней с одинаковой степенью, т.е. когда г1едгее [х] = !1едгее [пех1-х) = г1едгее [зга11пд [пех8-х)) . Эта ситуация обрабатывается так же, как и случай 1 — мы просто перемещаем указатели по списку. В следующей итерации цикла будет обработан случай 3 Часть Ч. Сложные структуры данна в) ММ)Н~) — ~()г) — --~"(7 ) — — — -э~15~ (25) (251 (33~ ® а3~ Омм) нььР некое де1'63()г) '«~ ~ ® ф~ 1555) б) вел) и) — ) г ) — — 3"® — Š— -мХ)— (25) ф ~А)) Щ )25) ~~)),) ® ® КФ(2225"') Э 45 (32) )24) ~~)) ГЗГ~,ьг ) г в) 6ем)Л) --~()23- — -э-;*'~)- — -~ )3. — — — ~))5' — — — — — — — — — — — ~(5) б)53 ~"253 ф) Я~ (33) Я д~29 ~~Я Я4 2 (5)",) Я) 23 ® Г~~г ® )1).') ци ав ~~5Э " 55 Рис.
19.4. Выполнение процедуры В)ном)Аь Нвлг 1)н)он или 4, когда объединяются второй и третий из трех корней с одинаковой степенью. В строке 10 выполняется проверка реализации случаев 1 и 2, а в строках 11-1 2— их обработка. Случаи 3 и 4 реализуются, когда х представляет собой первый из двух корней одинашвой степени, т.е. когда Недгее [х] = )гедгее [пехФ-х] ф Иедгее [азЫгид [пех5-х]] . Эти случаи могут возникнуть на любой итерации, в частности, всегда — непосредственно после обнаружения случая 2.
В случаях 3 и 4 мы связываем х и пехг-х. Различие между случаями 3 и 4 определяется тем, какой из этих узлов имеет меньший ключ и, соответственно, будет выступать в роли нового корня после связывания. В случае 3 (рис. 19.5в) )веу [х] < )веу [пех1-х], поэтому пех$-х привязывается к х. В строке 14 происходит удаление пех5-х из списка корней, а в строке 15 пехг-х становится крайним левым дочерним узлом х. В случае 4, показанном на рис.
19.5г, пехг-х имеет меньший ключ, так что х привязывается к пех5-х. В строках 1б-18 происходит удаление х из списка корней; Глава 19. Биномиальные пирамиды хе' '~ м жл х П Мад1Л! — -э312.— — -ъ(Л вЂ” — ~~ 3 '- — — — "э. 15 !- — — — — — — — — — — — — - — — Я~6 ! (16) ®,31) ф$2 233.! .,)- фй® %64 "1®Ф ® С~1 ия 3 вел-х !а 3еан 132! — — ~(12 ) — — -- — -э"(3 !"- -- — ! 115 '- — — — — — — — — — ~".6 ! 6 -.)":.".':,-,~--'.-'У' | ® (ф ~Ю;(23» (222') Я 313 ф» ;Ф5 ! 132 ! 1241~50) Я; ' е! Аеас 1Н1 — ~12) — — — — — --~3 !— (23) (Я 1255» — 6', фф ф ® Сэ> ии ! (41» в зависимости от того, является х первым элементом списка (строка 17) или нет (строка 18).
В строке 19 х делается крайним слева дочерним узлом пехг-х, а в строке 20 происходит обновление х для следующей итерации. Настройки для следующей итерации цикла 3тЫ1е после случаев 3 и 4 одинаковы. Мы должны просто связать два Вь-дерева в Вь+1-дерево, на которое указывает х. После него в списке может находиться от нуля до двух В~+1-деревьев, так что х теперь указывает на первое в последовательности из одного, двух или трех В1,+3-деревьев в списке корней. Если дерево только одно, на следующей итерации мы получаем случай 1: сергее [х) 36 11едгее (пехсх~1. Если х — первое из двух деревьев, то на следующей итерации получаются случаи 3 или 4. И наконец, если х — первое из трех деревьев, то в следующей итерации получаем случай 2.
Время работы процедуры Вичом1ль Нели 133ч1о3ч равно О (1к и), где п — общее количество узлов в биномиальных пирамидах Н1 и Нз. Убедиться в этом можно следующим образом. Пусть Н1 содержит 331 узлов, а Нз — пз узлов, так что и = п1 + 232. Тогда Н1 содержит не более ~18 3311+ 1 корней, а Нз — не более '(18 пзбг' + 1 корней. Таким образом, Н содержит непосредственно после вызова Часть Ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
