Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 120
Текст из файла (страница 120)
Недтее. Буден атрибут х. тагк указывает, были ли потери узлом х дочерних узлов начиная с момента, когда х стал дочерним узлом какого-то другого узла Вновь создаваемые узлы не помечены, а имеющаяся ~авва згм 54б Часть К Сложные структуры данньи пометка снимается, если узел становится дочерним узлом какого-то другого узла. До тех пор, пока мы не встретимся с операцией Рвскклзк-Кку в разделе 19.3, мы просто устанавливаем все атрибуты пьаг)с равными гльзв.
Обращение к данной фибоначчиевой пирамиде Н выполняется посредством указателя Н, т1п на корень дерева, содержащего минимальный ключ. Этот узел называется минимальным узлам (ппппппш поде) фибоначчиевой пирамиды. Если ключ с минимальным значением имеют более одного корня, то минимальным узлом может служить любой такой корень. Если фибоначчиева пирамида Н пуста„ то Н. ппп равен мп.. Корни всех деревьев в фибоначчиевой пирамиде связаны с помощью указателей 1е5г и пд61 в циклический дважды связанный слисок корней (гоо1 йа1) фнбоначчиевой пирамиды. Указатель Н, ппп, таким образом, указывает на узел списка корней, ключ которого минимален. Порядок деревьев в списке корней может быть любым.
Фибоначчиева пирамида, кроме того, имеет еще один атрибут — текущее количество узлов в фибоначчиевой пирамиде Н содержится в Н. и. Функция потенциала Как упоминалось, для анализа производительности операций над фибоначчиевыми пирамидами мы будем использовать метод потенциалов из раздела 17.3.
Для данной фибоначчиевой пирамиды Н обозначим через 1(Н) количество деревьев в списке корней Н, а через т(Н) — количество помеченных узлов в Н. Тогда потенциал Ф(Н) фибоначчиевой пирамиды Н определяется как (19.1) ф(Н) =1(Н) + 2т(Н) . (Подробнее об этой функции потенциала мы поговорим в разделе 19.3.) Например, потенциал фибоначчиевой пирамиды, показанной на рис.19.2, равен б + 2 . 3 = 11. Потенциал множества фибоначчневых пирамид представляет собой сумму потенциалов составлякицнх его пирамид. Будем считать, что единицы потенциала достаточно для оплаты константного количества работы, где константа достаточно велика для покрытия стоимости любой операции со временем работы 0(1).
Кроме того, предполагается, что приложение начинает свою работу, не имея ни одной фибоначчиевой пирамиды, так что начальный потенциал равен О и, в соответствии с формулой (19.1), во все последующие моменты времени потенциал неотрицателен. Из (17.3) верхняя граница общей амортиэированной стоимости является, таким образом, верхней границей общей фактической стоимости последовательности операций.
Максимальная степень Амортизационный анализ, который будет выполнен в оставшихся разделах главы, предполагает, что известна верхняя граница Р(п) максимальной степени любого узла в фнбоначчиевой пирамиде из и узлов. Мы не доказываем этого, но при поддержке только операций над объединяемыми пирамидами Р(п) < ~1б и(. 547 Глава!д Фчбочаччиевы лирамиды (В упр. 19.2,(г) читателям предлагается самостоятельно доказать зто свойство.) В разделах 19.3 и 19.4 мы покажем, что при дополнительной поддержке операций РескеАБе-Кеу и Рееете Р(п) = О(1б п).
19.2. Операции над объединяемыми пирамидами Операции над объединяемыми пирамидами в случае фибоначчиевых пирамид откладывают выполнение работы настолько, насколько это возможно. По сути, зто компромисс между реализациями различных операций. Например, мы вставляем узел, добавляя его в список корней, что требует только константного времени. Если начать с пустой фибоначчневой пирамиды и вставить в нее )с узлов, то фибоначчиева пирамида будет представлять собой просто список корней из к узлов. Компромисс заключается в том, что если затем мы выполняем над фибоначчиевой пирамидой Н операцию ЕхткАст-Меч, то после удаления узла, на который указывает Н. тт, мы должны просмотреть каждый из остающихся в списке корней й — 1 узлов в поисках нового минимального узла. Раз уж мы все равно должны пройти по всему списку корней в процессе выполнения операции ЕХТКАСТ-МИЧ, мы заодно собираем узлы в неубывающие деревья, чтобы уменьшить размер списка корней.
Мы увидим, что независимо от того, как выглядел список корней непосредственно перед выполнением операции ЕхтдАст-Мпч, после нее каждый узел в списке корней имеет степень, уникальную в пределах списка, а это приводит к тому, что размер списка корней не превышает Р(п) + 1.
Создание фибоначчиевой пирамиды Для создания пустой фибоначчиевой пирамиды процедура МАКЕ-Вв-НЕАЕ выделяет память и возвращает объект фибоначчиевой пирамиды Н, причем Н. и = О и Н. тт = мц.; деревьев в Н нет. Поскольку 1(Н) = О и т(Н) = О, потенциал пустой фнбоначчиевой пирамиды Ф(Н) = О. Таким образом, амортизированная стоимость процедуры МАке-Вв-НеАе равна ее фактической стоимости 0(1). Вставка узла Приведенная далее процедура вставляет узел х в фибоначчиеву пирамиду Н в предположении, что узлу уже выделена память и атрибут узла х.кеу уже заполнен. Часть Е Слажные струюпуры данныл 54о Н. пап (а) Рис.
19З. Вставка узла в фибоначчиеву пирамиду. (а) Фибоначчиева пирамщм Н. (б) Фибоначчиева пирамида Н после вставки узла с ключом 21. Узел становится собственным неубывающим деревом и добавляется в список юрнея, оказываясь левым братом юрия. Г1В-НВАР-11ззект(Н, х) 1 х.Неугее = 0 2 х.р = 141е 3 х.сЬзЫ = )41е 4 х.злого = РАЕЯЕ 5 ГН.нззп =9 ип. 6 Создать список корней Н, содержащий только х 7 Н.пззп = х 8 е1ве Вставить х в список корней Н 9 й'х.)сеу с Н.тзп.)сер 10 Н.пззп = х 11 Н.п = Н.п+ 1 В строках 1-4 инициализируются некоторые структурные атрибуты узла х. В строке 5 выполняется проверка, является ли фибоначчиева пирамида Н пустой. Если является, то в строках 6 и 7 узел х делается единственньзм узлом списка корней Н, а атрибут Н.
тзп получает значение, указывающее на х. В противном случае в строках 8-10 выполняются вставка х в список корней Н и при необходимости обновление атрибута Н. пззп. Наконец а строке 11 увеличивается значение Н. и, отражая добавление нового узла, На рис. 19.3 показана вставка узла с ключом 21 в фибоначчиеву пирамиду, приведенную на рис. 19.2. Для определения амортнзнрованной стоимости Р(В-НеАР-1хзект рассмотрим исходную фибоначчиеву пирамиду Н и фибоначчиеву пирамиду Н', которая получается в результате вставки узла. Тогда 1(Н') = ((Н) + 1 и зп(Н') = т(Н), и увеличение потенциала составляет ((1(Н) + 1) + 2 т(Н)) — (1(Н) + 2 т(Н)) = 1 . Поскольку фактическая стоимость равна О(1), амортизированная стоимость рав- на О(1) + 1 = О(1). Поиск минимального узла На минимальный узел фнбоначчневой пирамиды Н указывает указатель Н.
ппп, так что поиск минимального узла занимает время О(1). Поскольку по- 549 Глава!9. Фибаиаччиевы ииралчиды тенциал Н при этом ие изменяется, амортизированная стоимость этой операции равна ее фактической стоимости О(1). Обьединение двух фибоначчиевых пирамид Приведенная далее процедура объединяет фибоначчиевы пирамиды Н! и Нг, уничтожая их в процессе объединения. Процедура попросту соединяет списки корней Н! и Нг и находит затем новый минимальный узел.
По окончании работы объекты, представляющие Н! и Нг, далее использоваться не могут. Р !В-НВАР-АР!!О!4(Н!, Нг) 1 Н = МАКЕ-Р!В-НЕАРО 2 Н.гпт = Н!.т!и 3 Конкатенация списков корней Нг и Н 4 И (Н!. тгп == !ч!е) или (Нг тш ф !ч!е и Нг, твпЛееу < Н!. т!п.'кеу) 5 Н.т!п = Нг.твп 6 Н.п = Н!.и+Нг.п 7 гепзгв Н В строках 1-3 выполняется конкатенация списков корней фибоначчиевых пирамид Н! и Нг в новый список корней фибоначчиевой пирамиды Н. Строки 2, 4 и 5 устанавливают минимальный узел фибоначчиевой пирамиды Н, а в строке 6 определяется общее количество узлов Н. и.
Возврат полученной фибоначчиевой пирамиды Н вьпюлняется в строке 7. Как и в процедуре г!В-НВАР-1!4зект, все юрии остаются корнями. Изменение потенциала составляет ф(Н) — (ф(Н,) + ф(Н,)) = (!(Н) + 2 т(Н)) — ((!(Нг) + 2 т(Нг)) + (!(Нг) + 2 т(Нг))) =О, посюльку !(Н) = !(Н!)+!(Нг) и т(Н) = т(Н!)+т(Нг). Таким образом, амортизированная стоимость р!в-НВАР-13н!о!4 равна ее фактичесюй стоимости О(1). Извлечение минимального узла Процесс извлечения минимального узла наиболее сложный из всех операций, рассматриваемых в данном разделе.
Это также то место, где выполняются отложенные действия по объединению деревьев. Псевдокод процедуры извлечения минимального узла приведен ниже. Для удобства предполагается, что, когда узел удаляется из связанного списка, указатели, остающиеся в списке, обновляются, но указатели в извлекаемом узле остаются неизменными. В этой процедуре используется вспомогательная процедура Соызое!ВАте, которая будет рассмотрена чуть позже. Часть и Сложные структуры данные 550 Г!и-НеАР-ЕхткАст-М11ч(Н) 1 з = Н.ш(п 2 Из~МИ. 3 1ог каждый дочерний узел х узла х 4 Добавить х в список корней Н 5 х.р = ын. 6 Удалить г из списка корней Н 7 Ы з == з, т1дЫ 8 Н.т(п = ьш.
9 е!зе Н.т(п = г.пд)ьг 10 С о из ош и Ате (Н) 11 Н. п = Н. п — 1 12 гегигп з Как показано на рис. 19.4, процедура Гш-НеАЕ-ЕхткАст-Мпч сначала создает список корней из дочерних узлов минимального узла, а затем удаляет последний из списка корней. Затем выполняется уплотнение списка корней путем связывания корней одинаковой степени, пока в списке останется не больше одного корня каждой степени.
Работа начинается в строке 1, где в переменной з сохраняется указатель на минимальный узел фибоначчиевой пирамиды, — именно этот указатель процедура вернет в конце работы. Если з = и1е, это означает, что фибоначчиева пирамида Н пуста, и работа на этом заканчивается. В противном случае мы удаляем узел з из Н, делая все дочерние узлы узла г корнями в Н в строках 3-5 (помещая их в список корней) и вынося из него з в строке 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
