Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 116
Текст из файла (страница 116)
Циклический дважды связанный список (см. раздел 10.2) обладает двумя преимуществами для использования в фибоначчиевых пирамидах. Во-первых, удаление элемента из такого списка выполняется за время О (1). Во-вторых, если имеется два таких списка, их легко обьединить в один за то же время 0(1). В описании операций над фибоначчиевыми пирамидами мы будем неформально ссылаться на зти операции, оставляя читателю самостоятельно добавить все детали их реализации.
Глава 20. Фибоиаччиевы пирамиды 561 Кроме того, будут использоваться два других поля каждого узла. Количество дочерних узлов х хранится в поле сергее [х], а логическое значение тагес [х] указывает, были ли потери узлом х дочерних узлов начиная с момента, когда х стал дочерним узлом какого-то другого узла. Вновь создаваемые узлы не помечены, а имеющаяся пометка снимается, если узел становится дочерним узлом какогото другого узла. До тех пор, пока мы не встретимся с операцией РлсклАзл Клу в разделе 20.3, мы считаем поле тагй всегда равным ьАьзп. Обращение к данной фибоначчиевой пирамиде Н выполняется посредством указателя т(п [Н] на корень дерева с минимальным ключом.
Этот узел называется минимальным узлам (т(пппшп поде) фибоначчиевой пирамиды. Если фибоначчиева пирамида Н пуста, то тт [Н] = мп.. Корни всех деревьев в фибоначчиевой пирамиде связаны при помощи указателей 1е1г и пдйс в циклический дважды связанный список корней (гоос 1ы) фибоначчиевой пирамиды. Указатель тт [Н], таким образом, указывает на узел списка корней, ключ которого минимален.
Порядок деревьев в списке корней произволен. Фибоначчиева пирамида, кроме того, имеет еще один атрибут — текущее количество узлов в фибоначчиевой пирамиде Н хранится в и [Н]. Потенциальная функция Как упоминалось, мы будем использовать метод потенциалов из раздела 17.3 для анализа производительности операций над фибоначчиевыми пирамидами. Для данной фибоначчиевой пирамиды Н обозначим через $ (Н) юличество деревьев в списке юрней Н, а через т (Н) — количество помеченных узлов в Н. Тогда потенциал фибоначчиевой пирамиды Н определяется как Ф(Н) = г(Н)+2т(Н). (20.1) (Подробнее о потенциале мы поговорим в разделе 20.3.) Например, потенциал фибоначчиевой пирамиды, показанной на рис.
20.1, равен б+ 2 3 = 11. Потенциал множества фибоначчиевых пирамид представляет собой сумму потенциалов составляющих его пирамид. Будем считать, что единицы потенциала достаточно для оплаты константного количества работы, где юнстанта достаточно велика для покрытия стоимости любой операции со временем работы О (1). Кроме того, предполагается, что приложение начинает свою работу, не имея яи одной фибоначчиевой пирамиды, так что начальный потенциал равен 0 и, в соответствии с формулой (20.1), во все последующие моменты времени потенциал неотрицателен. Из (17.3) верхняя граница общей амортизироваиной стоимости является, таким образом, верхней границей общей фактичесюй стоимости последовательности операций.
562 Часть Ч. Сложные структуры данньк Максимальная степень Амортизационный анализ, который будет выполнен в оставшихся разделат главы, предполагает, что известна верхняя граница .Р (ть) максимальной степени узла в фибоначчиевой пирамиде из п узлов. В упражнении 20.2-3 надо показать, что при поддержке только лишь операций сливаемых пирамид Р(п) < ~1бп). В разделе 20.3 мы покажем, что при дополнительной поддержке операций Ве. скплзе Кпу и 13н.нп Р(п) = 0(!яп). 20.2 Операции над еливаемыми пирамидами В этом разделе мы опишем и проанализируем операции над сливаемыми пирамидами в применении к фибоначчиевым пирамидам.
Если поддерживаются только операции Млкн Нила, 1нзнкт, Мппмцм, Ехтллст Мпч и Ычюн, то кажлвя фибоначчиева пирамида представляет собой набор неупорядоченных биномиаль. ных деревьев. Неуиорядочеииое бииомиальиое дерево (ипогдегед Ь1пош1а! нее) похоже на обычное биномиальное дерево и определяется рекурсивно подобно ему. Неупорядоченное биномиальное дерево Уо состоит из единственного узла, а неупорядоченное биномиальное дерево Уь состоит из двух неупорядоченных биномиальных деревьев Уь ь причем корень одного из них является произвольным дочерним узлом корня другого. Лемма 19.1, в которой описаны свойства биномя.
альных деревьев, применима и к неупорядоченным биномиальным деревьям, но со следующей вариацией свойства 4 (см. упражнение 20.2-2): 4'. В неупорядоченном биномиальном дереве Уь корень имеет степень 1с, которая превышает степень любого другого узла. Дочерними узлами корня являются корни поддеревьев Уо, Ум..., Уь 1 в некотором порядке.
Таким образом, если фибоначчиева пирамида с п узлами представляет собой набор неупорядоченных биномиальных деревьев, то Р (ть) = ()б и). Ключевая идея применения операций над сливаемыми пирамидами к фибоначчиевым пирамидам состоит в том, чтобы по возможности отложить работу на как можно более позднее время. По сути это компромисс среди реализаций различных операций.
Если количество деревьев в фибоначчиевой пирамиде невелико, то в процессе выполнения операции Ехтклст Мпч мы можем быстро определить, какой из оставшихся узлов становится минимальным. Однако, как мы видели в упражнении 19.2-10, в случае биномиальных пирамид мы должны заплатить определенную цену за то, что деревья остаются небольшими: требуется время й (1к и) для того, чтобы вставить узел в биномиальную пирамиду или объединить две биномиальные пирамиды в одну.
Как мы увидим, мы не будем пытаться объединять деревья в фибоначчиевых пирамидах при вставке новою узла или слиянии двух пирамид. Такое объединение сохраняется только в операции Глава 20. Фибоначчиевы пирамиды 563 Ехтклст Мпч, когда нам действительно нужно будет искать новый минималь- ный узел.
Создание новой фибоначчиевой пирамиды Для создания пустой фибоначчиевой пирамиды процедура МАке Р1в НеАР выделяет память и возвращает объект фнбоначчиевой пирамиды Н, причем п [Н] = 0 и тзп [Н] = 1ч1 . Деревьев в Н нет. Поскольку 1(Н) = 0 и т (Н) = = О, потенциал пустой фибоначчиевой пирамиды Ф(Н) = О.
Таким образом, амортизированная стоимость процедуры МАке Р1в НВАР равна ее фактической стоимости О (1). Вставка узла Приведенная далее процедура вставляет узел х в фибоначчиеву пирамиду Н в предположении, что узлу уже выделена память и поле узла йеу[х] уже заполнено. Р1В НЕАР 1хБЕКТ(Н, х) 1 Ыедгее [х] + — 0 р[х] -И1Ь З сЫИ[х] — 1Ч1Ь 4 1е71[х] — х 5 г1дЫ[х] — х 6 тагй[х] +- РА1.БЕ 7 Присоединение списка корней, содержащего х, к списку корней Н 8 н тзп[н] = 1ч1ь или Йеу[х] ( Йеу[т1п[н]] 9 1йеп т1п[Н] — х !О п[Н] +- п[Н] + 1 После того как в строках 1-6 выполняется инициализация полей узла х, создающая собственный циклический дважды связанный список, в строке 7 выполняется добавление х к списку корней Н за фактическое время О (1).
Таким образом, узел х становится деревом из одного узла в составе фибоначчиевой пирамиды. Он не имеет дочерних узлов и не помечен. В строках 8-9 происходит (если оно необходимо) обновление указателя на минимальный узел, а в строке 10 увеличивается значение общего количества узлов в фибоначчиевой пирамиде п [Н] (что отражает добавление нового узла). На рис.
20.2 показана вставка узла с ключом 21 в фнбоначчиеву пирамиду, представленную на рис. 20.1. В отличие от процедуры Впчом1Аь НеАР 1МБект, процедура Р1В НеАР 114Бект не пытается объединять деревья в фибоначчиевой пирамиде. Если последовательно будут выполнены и операций Р1в НВАР 11чзект, то к списку корней будут добавлены к деревьев, состоящих из одного узла. Часть Ч. Сложные структуры данных 564 Яи! Ц! Рис. 20.2. Вставка узла в фнбоначчиеву пирамиду Для определения амортизированной стоимости процедуры Р)в НВАР 1)чзект рассмотрим исходную фибоначчиеву пирамиду Н и фибоначчиеву пирамиду Н', которая получается в результате вставки узла.
к(Н') = в(Н) + 1 и т(Н') = = т (Н), и увеличение потенциала составляет (($ (Н) + 1) + 2т (Н)) — (т (Н) + 2т (Н)) = 1. Посюльку фактическая стоимость равна О (1), амортизированная стоимость рав- на 0 (1) + 1 = 0 (1). Поиск минимального узла На минимальный узел фибоначчиевой пирамиды Н указывает указатель тт [Н], так что поиск минимального узла занимает время О (1). Поскольку потенциал Н при этом ие изменяется, амортизированная стоимость этой операции равна ее фактичесюй стоимости 0 (1). Объединение двух фибоначчиевых пирамид Приведенная далее процедура объединяет фибоначчиевы пирамиды Н! и Нз, попросту соединяя списки юрней Н! и Нз и находя затем новый минимальный узел: Р!В НБАР ПМО)ч(Н), Нз) 1 Н ~ — МАКЕ Р)В НЕАРО 2 тт[Н] — тт[Н)] 3 Добавление списка корней Нз к списку корней Н 4 и (твп[Н)] = ып.) или (твп[Нз] ф )ч)ь и йер[твп[Нз]] < )веу[твп[Н)]]) 5 тЬеп твп[Н] - твп [На] 6 п[Н] в- п[Н)] + п[Нз] 7 Освобождение обьектов Н! и Нз Е гевпгп Н Глава 20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
