Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 114
Текст из файла (страница 114)
Сложные структуры данныи 550 р«е -х «еех«-х аписа,«п«««-х« --п»1Р— — -. ф.— --«.'«Р- — -и ~ф---~ р«с«-« х псх«-х — "" — 7~--- е---Ф- л Е' ~1 Г« р«е . х х хпхрх хпмпх«ме«рх! и — ---«ф» — — ъ-~ф -- — -«хф — — + — -л л пел«-л спе«-х В; «« р е«-.«х пех«х пйпх,рпех««/ »1 --~ ~«« — — М~ - — — «~х —.- -«.ф — —.) р:. з и'..'.~ ' ' 1 ! ',. ~ В, В„ В, ле«Ч«~ и пе«п«~е««.х~ х пех»х — '6-. — — — '«~1В- — -'ф — ' Й р«е«.х х пех«-х иИюп(пехпх1 о - — »ф — — ~Ф- -~Я- — —:" ф---~' п«х«х « ~ф-. — л /'~ рпсе.х х ер Я[1 В, В, В Иер В«1 псу~се и- «~ Рис.
19.5. Четыре случая, возможных при выполнении процедуры Впчом[А~ НВАР Ун! ОВ Впчом!Ае НеАР Мекоене более [15п«]+[!бпз1+2 < 2 [1ярх]+2 = О(15«и) корней. Следовательно„время работы процедуры Впчомьи Нелв Мекое составляет О (1к и). Каждая итерация цикла и Ы1е требует О (1) времени, и всего выполняе1- ся не более [15 п11' + [1я пз1' + 2 итераций, поскольку каждая из них в конечном счете приводит к перемещению указателя на одну позицию в списке корней Н или к удалению корня из списка. Отсюда следует, что общее время работы процедуры Впчомы.
НеАР Умом равно О(1йп). Впчом!Ае НБАР 1«чБект(Н, х) 1 Н е — МАКЕ В!ХОМ!АЕ НЕАР() р[х] -хп. 3 сйиЫ[х] — хп. Вставка узла Приведенная далее процедура вставляет узел х в биномиальную пирамиду Н (предполагается, что для х уже выделена память и поле Йер [х] уже заполнено): Глава 19. Биномиальные пирамиды 551 4 вгЫгпд1х) - !ч!Ь 5 !1едгее[х) — О б 7!еай'1Н'~) — х 7 Н + — В!ыОм!А1. НБАР 1!и!01ч(Н, Н ) Процедура просто создает биномиальную пирамиду Н' с одним узлом за время 0(1) и объединяет ее с биномиальной пирамидой Н, содержащей п узлов, за время 0 (1кп).
Вызов В!ыом!и. НеАР Ш~1оы должен освободить память, выделенную для временной биномиальной пирамиды Н'. (Реализация вставки узла без привлечения процедуры В!14ом1Аь НеАР 1)ы!О1ч оставлена читателю в качестве упражнения 19.2-8.) Извлечение вершины с минимальным ключом Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной пирамиды Н и возвращает указатель на извлеченный узел: В!ыОм!Аь НеАР ЕхткАст М!ы(Н) 1 Поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из списка корней Н 2 Н' 4- Млке Впчом!Аь НеАРО 3 Обращение порядка связанного списка дочерних узлов х, установка поля р каждого дочернего узла равным !чп.
и присвоение указателю аеа<!'1Н'1 адреса заголовка получающегося списка 4 Н < — В11чОм!Ае НБАР П1ч!Оы(Н, Н') 5 гетпгп х Процедура работает так, как показано на рис. 19.6. Исходная биномиальная пирамида Н показана на рис. 19.ба. На рис. 19.6б показана ситуация после выполнения строки 1: корень х с минимальным значением ключа удален из списка корней Н. Если х является корнем Вь-дерева, то, в соответствии со свойством 4 из леммы 19.1, потомками х слева направо являются корни биномиальных деревьев Вь 1, Вь з,..., Во. На рис. 19.6в показано, что, обращая порядок потомков узла х в строке 3, мы получаем биномиальную пирамиду Н', которая содержит все узлы дерева х, за исключением самого х.
Поскольку корень х удален из Н в строке 1, биномиальная пирамида, полученная в результате слияния Н и Н' в строке 4 (показанная на рис. 19.6г), содержит все узлы, которые изначально содержались в Н, кроме узла х. И наконец, в строке 5 процедура возвращает значение х. Поскольку строки 1-4 требуют для выполнения в случае биномиальной пирамиды Н с и узлами время 0 (1к и), время работы процедуры В!ыОм!Аь НБАР ЕхткАст М!и равно 0(1кп). Часть Ч. Сложные структуры данна 552 а) 6еаа)л! — — «е37) — — — е )9)- — — — — — — — — — — — — — «ее)у !еа! ) )263) 6)3) ] 6 ~ [)6 ееф~23) ® Я'(Н~ !27) )26] ® ))3) О)! 7)7) )36) ® )2е7) е .® )')6 )2 ® С 'В 6623,) а26 ЮЗ~ 6Ь и ® )36) '4$ ф 6) зеаа)!д — е )37е) — — — ~юе) ф ®® б ыы )и'! — -«625у — - е (ы2) — — е ()6) — — — — — е еа ЕЕ 4е7'Ее) ЕГИ'а) фл )Щф )36) фф а) ай)И! — е ~37е — — — -3 ')6! )- ~28» )!3 ® е) аеая! Л! — е.® — - — — - )2 — — — — — — — -- — — — — М 6 ~ 37 ® ф- ~6!'))4)® ® ~~в' ~АЗ © фф ),'36е) ~~~~)23 ® )42) Рис.
19.6. Работа процедуры В)НОМЫ. НЕАР ЕХТКАСТ МЛ4 Уменьшение ключа Впе)ОМ!А1. НЕАР ПЕСКЕАБЕ КЕУ(Н, х> Й) 1 и Й > Йеу[х] 2 1Ьеп еттог "Новый ключ больше текущего" 3 Йеу[х] — Й 4 уе — х 5 г +- р[у] 6 ие1611е я ф )4! и Йеу[у] < Йеу[я] 7 оо Обменять Йеу[у] е Йеу[я] Приведенная далее процедура уменьшает значение ключа узла х в биномяальной пирамиде Н, присваивая ему новое значение Й. В случае, если значение Й превышает текущий ключ х, процедура сообщает об ошибке. Глава 19. Биномиальные пирамиды 553 94~8 и маи 101 — ь®вЂ” ~~~ 6)~ ~Р .ВФФ веа~йй ФФ Рис.
19.7. Работа процедуры ВйчОМ!ль НеАР Вескелзе Кеу с Если у и г содержат сопутствующую 1> информацию, обменять также и ее у+ г г — р[у[ 8 9 10 11 Как показано на рис. 19.7, данная процедура уменьшает значение ключа так же, как и в бинарной неубывающей пирамиде — путем "всплывания" ключа в пирамиде. После того, как мы убедимся, что новый ключ не превышает текущий, и присвоим его х, процедура идет вверх по дереву. Изначально значение у равно х.
В кюкдой итерации цикла иййе в строках 6-10 значение кеу[у[ сравнивается со значением ключа родительского по отношению к у узла г. Если у является корнем или йеу [у[ > /сеу [г[, бнномиальное дерево является упорядоченным в соответствии со свойством неубывающей пирамиды. В противном случае узел у нарушает свойство неубывающей пирамиды и происходит обмен ключами и сопутствующими данными между узлами у и г, после чего процедура присваивает переменной у значение г и в очередной итерации переходит на един уровень вверх. Часть Ч.
Сложные структуры данньп 554 Процедура В!ыом!А1 НеА1' 13ескеАзе Кеу выполняется за время 0(18п), В соответствии со свойством 2 леммы 19.1, максимальная глубина х равна 118 и), так что цикл зтЬ11е в строках 6-10 выполняется не более (18 п3' раз. Удаление ключа Удаление ключа х и сопутствующей информации из биномиальной пирамиды Н легко выполняется за время 0(18п). В приведенной ниже реализации этой операции предполагается, что ни один узел в биномиальной пирамиде не имеет ключ со значением -оо.
ВпчОм!Ас НБАР Пеняете(Н, х) 1 ВечОм1АЕ НеАР 1уескеАБе Кеу(Н, х, — оо) 2 В!мОм1АС НеАР ЕхткАст Меч(Н) Процедура Вечом1АС НеАР ПескеАзе Кеу делает узел х единственным узлом с минимальным ключом в биномиальной пирамиде, равным — со (в упражнении 19.2-6 рассматривается ситуация, когда — со не может использоваться в качестве ключа даже временно).
Затем этот ключ и связанные с ним сопутствующие данные "всплывают" в биномиальной пирамиде до корня в процедуре В!ком!Ай НеАР ь!ескеАБе Кеу, после чего этот корень удаляется из дерева вызовом процедуры ВПЧОМ!Аь НЕАР ЕХТКАСТ МПЧ. Время работы процедуры Вечом1АЕ Нелв Пи.ете равно 0 (1к и). Упражнения 19.2-1. Напишите псевдокод процедуры Впчомы. НеАР Мекое. 19.2-2. Покажите, какая биномиальная пирамида получится в результате вставки узла с ключом 24 в биномиальную пирамиду, показанную на рис.
19.6а 19.2-3. Покажите, какая биномиальная пирамида получится в результате удаления узла с ключом 28 из биномиальной пирамиды, показанной на рис. 19.7в. 19.2-4. Докажите корректность процедуры Впчом!м, НеАР Шпон при помощи следующего инварианта цикла. В начале каждой итерации цикла ттЬ11е в строках 9-21 х указывает на корень, который представляет собой: ° либо единственный корень с данной степенью; ° либо первый из всего двух корней данной степени; ° либо первый или второй из всего трех корней данной степени. Глава 19. Бнномнальные пирамиды 555 Кроме того, все корни, являющиеся предшественниками предшественника х в списке корней, единственные со своими степенями в списке корней, и если предшественник х имеет степень, отличную от степени х, то эта степень также единственна в списке корней. И, наконец, степени узлов монотонно увеличиваются в процессе прохода по списку корней. Предположим, что нет никакой возможности представления ключа со значением — оо.
Перепишите процедуру В!ыом1Аь НеАР 13еьете так, чтобы она корректно работала в указанной ситуации. Время работы про- цедуры должно составлять О (18 и). 19.2-6. Рассмотрите взаимосвязь между вставкой в биномиальную пирамиду и увеличением представляющего ее двоичного числа, а также между сли- янием двух биномиальных пирамид и суммированием двух двоичных чисел. 19.2-7. 19.2-8. С учетом результатов упражнения 19.2-7, перепишите процедуру В1ыом1Аь НеАР 1хзект таким образом, чтобы для вставки узла в бииомиальную пирамиду не требовался вызов В!ном!АЕ НеАР 1)ы10х. Покажите, что если список корней поддерживается в строго убывающем порядке по степеням (вместо строго возрастающего порядка), то все опе- рации с биномиальными пирамидами можно реализовать без изменения их асимптотического времени работы. 19.2-9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
