Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 119
Текст из файла (страница 119)
Гибас (бшЬаз) и Седжвик (154] рассмотрели взаимосвязи между различными видами сбалансированных деревьев, включая красно-черные деревья и 2-3-4-деревья. В 1970 году Хопкрофт ввел понятие 2-3-деревьев, которые были предшественниками В- и 2-3-4-деревьев и в которых каждый внутренний узел имел 2 или 3 дочерних узла. В-деревья предложены Баером (Вауег) и Мак-Крейтом (МсСге(яЬг) в 1972 году (34] (выбор названия для своей разработки они не пояснили).
Бендер (Вепбег), Демейн (1)ешаше) и Фарах-Колтон (ЕагасЬ-С011оп) (39] изучили производительность В-деревьев при наличии иерархической памяти. Алгоритмы с игнорированием кешировиния (сасйе-оЫ10(опз) эффективно работают без явного знания о размерах обмена данными между различными видами памяти. Имеесся русселя перевод: Д. Кяуя Исяусстео лросречччроеолш, м. Я Сортороеяа ч лолсл, 2-е чяд.— Мс И.Д. "Вильямс", 2000. Глава 19. Фибоначчиевы пирамиды Пирамиды Фибоначчи служат двум целям. Во-первых, они поддерживают набор операций, составляющих то, что известно под названием "объединяемые, или сливаемые, пирамиды" (шегкеаЫе Ьеар). Во-вторых, некоторые операции в фибоначчиевых пирамидах выполняются за константное амортизированное время, что делает эту структуру данных хорошо подходящей для приложений, в которых часто применяются данные операции.
Обьеднняемые пирамиды Ооъедиилемой пирамидой является любая структура данных, поддерживающая следующие операции, в которых каждый элемент имеет ключ )сеу. Млке-Недр() создает и возвращает новую пирамиду, не содержащую элементов. 1рузект(Н,х) вставляет в пирамиду Н элемент х, ключ /сеу которого к этому моменту заполнен. М!ру!мгам(Н) возвращает указатель на элемент пирамиды Н, ключ которого минимален. Ехтклст-Мпч(Н) удаляет из пирамиды Н элемент, ключ которого минимален, и возвращает указатель на этот элемент. 11пуюм(НМ Нз) создает и возвращает новую пирамиду, которая содержит все элементы пирамид Нг и Нз. Пирамиды Ну и Нз этой операцией "уничтожаются".
В дополнение к перечисленным выше операциям с обьединяемыми пирамидами пирамиды Фибоначчи поддерживают еще две операции. (лескелее-Кеу(Н,х,)с) назначает элементу х в пирамиде Н новое значение ключа lс, которое не больше его текущего значения.' РЕЕЕТЕ(Н, х) удаляет элемент х из пирамиды Н. 'Как упоминалось во введении к части т', по умолчанию рассматриваемые в книге обьединаемые пирамиды вюжютса обьедннаемыми неубывающими пирамидами, так что к ним применимы операции Мнимом, Ехтклст-Мш и Оесаелве-Кеу. Можно точна так же определить обьединлемые невоарастающие пирамиды с операиивми МАХЬМПМ, ЕхткАСт-МАХ и Унскелан-кет.
Глава!9. Фибоиаччиеаы пирамиды 543 Процедура Бинарная пирамида Фибоначчиева (наихудший пирамида случай) (амортизированная) ~(1) Н(1я и) ~(1) ед(1б и) с1(п) 9(1б и) 9(!б и) ~(1) Н(1) ст(1) О(!я п) ~(1) ст(1) О(!я п) МАке"НВАР 1гчоЕКТ М!Х1М13М Ехткдст-М1ы с)гч!ОХ РескеАЯе-Кеу Реьете Рне. 19.1. Время выполнения операций в двух реализациях объединяемых пирамид. В момент выполнения операции количество элементов пирамиды (или пирамид) равно и. Фибоначчиевы пирамиды в теории и на практике С теоретической точки зрения фибоначчиевы пирамиды особенно полезны в случае, когда количество операций Ехткдст-М114 и Рееете относительно малб по сравнению с количеством других операций.
Такая ситуация возникает во многих приложениях. Например, некоторые алгоритмы в задачах о графах могут вызывать процедуру Рескедбе-Кеу по одному разу для каждого ребра. В плотных графах с большим количеством ребер амортизированное время выполнения Рескедзе-Кет, равное тэ(1), представляет собой существенный выигрыш по сравнению со временем Н(!я п) в наихудшем случае в биномиальных пирамидах. Быстрые алгоритмы для таких задач, как поиск минимального остовного дерева Как показано в таблице на рис.19.1, если операция Ш41о1ч не требуется, то вполне можно воспользоваться обычной бинарной пирамидой, которая, например, применялась в пирамидальной сортировке (см. главу б).
Прочие, отличные от НМ1ОМ, операции в бинарной пирамиде выполняются в наихудшем случае за время О(!яп). Однако при необходимости операции Шчю1ч производительности бинарной пирамиды недостаточно. В случае конкатенации массивов, хранящих обьединяемые бинарные пирамиды, с последующим выполнением процедуры Во1ео-М1м-Недр (см. раздел б.З) процедура 1)мю1ч в наихудшем случае выполняется за время тд(п). С другой стороны, фибоначчиевы пирамиды имеют лучшие, чем у бинарных пирамид, асимптотические времена работы операций 1мбект, 1!141о!ч и !Зескедзе-Кеу н такие же времена работы прочих операций, как и у бинарных пирамид. Заметим, однако, что времена работы для фибоначчиевых пирамид на рис. !9.! представляют собой амортнзированные значения, а не границы для наихудшего случая.
Операция 1!1ч1ом в фибоначчиевой пирамиде требует для выполнения константного амортизированного времени, что значительно лучше, чем линейное время в наихудшем случае, требующееся в случае бинарной пирамиды (конечно, в предположении достаточности амортизированного времени работы).
Часть Г Слалсные структуры данлыл (глава 23) или поиск кратчайших путей из одной вершины (глава 24), преимущественно опираются на фибоначчиевы пирамиды. Однако с практической точки зрения программная сложность реализации и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых пирамид, делая их для большинства приложений менее привлекательными, чем обычные бинарные (или й-арные) пирамиды. Таким образом, интерес к фибоначчиевым пирамидам, в первую очередь, сугубо теоретический. Широкое практическое использование могла бы получить более простая структура данных, но обладающая тем же амортизнрованным временем работы, что и фибоначчиевы пирамиды. И бинарные, н фибоначчиевы пирамиды недостаточно эффективно выполняют операцию поиска Белксн; поиск элемента с заданным ключом может занять некоторое время.
Именно поэтому такие операции, как Пескелзе-Кет или Рн.ете, которые обращаются к конкретному элементу, требуют в качестве входных данных указатель на этот элемент. Как и в нашем рассмотрении очередей с приоритетами в разделе 6.5, при использовании в приложении сливаемых пирамид зачастую в каждом элементе пирамиды хранится идентификатор соответствующего объекта приложения, а идентификатор элемента пирамиды — в объекте приложения. Точная природа этих идентификаторов зависит от приложения и его реализации. Подобно ряду других рассмотренных структур данных, фибоначчиевы пирамиды основаны на корневых деревьях. Мы представляем каждый элемент узлом в дереве, и каждый узел имеет атрибут яеу.
В оставшейся части данной главы мы вместо термина "элемент" будем использовать термин "узел". Мы также проигнорируем вопросы выделения памяти для узла перед его вставкой и освобождения памяти после удаления, считая, что ответственность за эти действия возложена на код, вызывающий процедуры пирамиды. В разделе 19.1 определяются фибоначчиевы пирамиды, рассматриваются их представление и функция потенциала, используемая в процессе выполнения амортизационного анализа.
В разделе 19.2 показано, как реализовать операции объединяемых пирамид, получив при этом амортизированные времена работы, показанные на рис. 19.1. Две оставшиеся операции, Ресв.еязе-Кет и Эе~.еге, рассматриваются в разделе 19.3. Наконец, в разделе 19.4, завершается ключевая часть анализа, а также поясняется происхождение названия рассматриваемой структуры данных.
19.1. Структура фибоиаччиевых пирамид Фнбоначчиева пирамида (г(Ъопасс1 Ъеар) представляет собой набор корневых деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды, т.е. каждое дерево подчиняется этому свойству: ключ узла не меньше ключа его родителя. На рис. 19.2, (а) показан пример фибоначчневой пирамиды.
Глава РД Фибгиаччиввы аиразаи)ы Н. тзп (а) ~~~ ----(фзг- —. "фга-"----- ----4~!у . - . " Ф~~. б дз:Ф ~Ь Яб) ~ф Рнс. 19Л. (а) Фибоначчиева пирамида, состоюцвя нз впи деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. и чегырнаыютн узлов. Пунктирная линия указывает корневой список. Мннимальнмм узлом нирамнаы является узел, содериищий ключ 3.
Помеченные узлы показанм черным цветом. Потенциал двиной конкретной фибоначчиевой пирамиды рами 5+ 2 . 3 = 11. (6) Более полное представление, показывающее указатели р (стрелки вверх), сЫИ (стрелки вина) н (езг и г(9)зг (горизонтальные стрелки). на прочих рисунках главы зтн детали опущены, поскольку вся указанная информация макет быть восстановлена нз схемы наподобие приведенной в части (а). Как показано на рис. 19.2,(б), каждый узел х содержит указатель х.
р на родительский узел и указатель х. сЬзЫ на некоторый нз дочерних узлов. Дочерние узлы узла х циклически соединены в двусвязный список, который мы называем дочерним списком узла х. Каждый дочерний узел у в дочернем списке имеет указатели д.1е1( и у.г(дЫ, щпорые указывают на левый и правый "братские" узлы узла у соответственно. Если узел у имеет только один дочерний узел, то д. 1е1( = у.гздЫ = у. Дочерние узлы в дочернем списке могут находиться в любом порядке. Циклический дважды связанный список (см.
раздел 10.2) обладает двумя преимуществами для использования в фибоначчиевых пирамидах. Во-первых, удаление злемента из такого списка выполняется за время 0(1). Во-вторых, если имеется дна таких списка, их лепю обьединнть в один за то же время О(1). В описании операций над фибоначчиевыми пирамидами мы будем неформально ссылаться на зги операции, оставляя читателю самостоятельно добавить все детали нх реализации. Каждый узел имеет два других атрибута. Мы храним количество дочерних узлов в дочернем списке узла х в х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
