Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 115
Текст из файла (страница 115)
Приведите пример входных данных, для которых процедуры В!!чом!Аь НеАР ЕхткАст М1х, В!ыом1Аь НеАР 13ескеАзе Кеу, В!!чом!Аь НеА1' Уы!Оы и В1хом1Аь НеАР 1Эеьете выполняются за время й (18п). Поясните, почему время работы процедур В!хом!АЕ НеАР 1ызект и В!ыо- М1А!. НеАР Мп пм!!м в худшем случае составляет й (18 и), а не й (18 и) (см. задачу 3-5). 19.2-10. Задачи 2-3-4-пирамиды В главе 18 рассматривались 2-3-4-деревья, в которых каждый внутрен- ний узел (кроме, возможно, корня) имеет два, три или четыре дочерних узла, и все листья таких деревьев располагаются на одной и той же глу- бине. В данной задаче мы реализуем 2-3-4-пирамиды, поддерживающие операции сливаемых пирамид. 19-1.
19.2-5. Поясните, почему процедура В!ыом!и. НЕАР М1ы!м!!м может работать некорректно, если ключ может иметь значение оо. Перепишите псевдокод так, чтобы он корректно работал и в указанной ситуации. Часть Ч. Сложные структуры данных 556 2-34-пирамиды отличаются от 2-34-деревьев следующим. В 2-3-4-пирамидах ключи хранятся только в листьях, и в каждом листе х хранится ровно один ключ в поле Ьеу [х]. Никакой порядок ключей в листьях не соблюдается, т.е. при перечислении слева направо ключи могут располагаться в произвольном порядке.
Каждый внутренний узел х содержит значение атаП [х], юторое равно минимальному значению среди ключей листьев поддерева, корнем юторого является х. Корень г содержит поле ЬездЬ1 [г], в котором хранится высота дерева. И наконец, 2-3-4-пирамиды предназначены для хранения в оперативной памяти, так что при работе с ними не требуются никакие операции чтения или записи на диск. Реализуйте перечиспенные далее операции над 2-3-4-пирамидами. Каждая из операций а-д должна выполняться за время О (!я и) при работе с 2-3-4-пирамидой, в которой содержится и элементов. Операция 0н!он в части е должна выполняться за время 0(!яи), где и — количество элементов в двух входных пирамидах.
а) Операция Мммпм возвращает указатель на лист с наименьшим значением ключа. б) Операция РпскнАзп Кит уменьшает значение ключа в данном листе х до указанного значения Ь < Йеу[х]. в) Операция 1мзпкт вставляет в пирамиду лист х с ключом /с. г) Операция ОН.втн удаляет из пирамиды лист х. д) Операция Ехтклст М!и извлекает из пирамидылистс наименьшим значением ключа. е) Операция Пч!ом объединяет две 2-34-пирамиды, возвращая образующуюся в результате слияния 2-3-4-пирамиду, уничтожая при этом входные пирамиды. 19-2. Алгоритм минимального остовного дерева с использованием биномиапьных пирамид В главе 23 представлены два алгоритма для решения задачи поиска минимального остовного дерева неориентированного графа. Сейчас мы рассмотрим, каким образом для решения этой задачи можно использовать биномиапьные пирамиды.
Пусть задан связный неориентированный граф С = (К Е) с весовой функцией и: Е -+ В„которая ставит в соответствие каждому ребру (и, и) его вес и (и, и). Мы хотим найти минимальное остовное дерево графа С, т.е. ацикличесюе подмножество Т С Е, которое соединяет все вершины У и чей общий вес ш(Т) = ~~) ю(и,и) 1н,и)ет является минимальным. Глава 19. Биномиальные пирамиды 557 Далее приведен псевдокод (корректность которого можно доказать с использованием методов из раздела 23.1), строящий минимальное остовное дерево Т.
Программа хранит разбиение (У;) множества вершин У, а для каждого множества У, — множество ребер, инцидентных вершинам в Уб Е; С ((и, о): и Е У, или и Е У;) . МБТ(С) Т -6 2 1ог (Для) каждой вершины тч Е У[С] 3 оо У вЂ” (о,) 4 Е1 +- ((оо о) Е ЕЩ 5 и Ьйе (Пока) имеется более одного множества У; 6 оо Выбор произвольного множества Уз 7 Извлечение ребра (и, е) с минимальным весом из Е; 8 Без потери общности полагаем и е У, и е е У' 9 И'1фу 1О 1Ьеп Т вЂ” ТО ((и,и)) 11 У, + — У; 0 Уч уничтожение У. 12 Опишите, как реализовать этот алгоритм с использованием биномиальных пирамид для управления множествами вершин и ребер.
Требуется ли внесение изменений в представление биномиальных пирамид? Требуется ли добавление к операциям, перечисленным в табл. 19.1, других операций над биномиальными пирамидами7 Оцените время работы вашей реализации алгоритма. Заключительные замечания Биномиальные пирамиды были разработаны в 1978 году Внллемином (чп111еплп) [307).
Детальное описание их свойств представлено в работах Брауна (Вговп) [49, 50). ГЛАВА 20 Фибоначчиевы пирамиды В главе 19 мы познакомились с биномиальными пирамидами, для которых время выполнения операций 1мзвкт, Мммим, Ехтклст М1н, льном, а также 13нскяАзв Кву и Рвытк в худшем случае равно О (1б п). В этой главе мы познакомимся с фибоначчиевыми пирамидами, которые поддерживают тот же набор операций, но имеют то преимущество, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное О (1). С теоретической точки зрения фибоначчиевы пирамиды особенно полезны в случае, когда количество операций ЕхткАст Мпч и Реьнтв относительно мало по сравнению с количеством других операций. Такая ситуация возникает во многих приложениях.
Например, некоторые алгоритмы в задачах о графах вызывают процедуру РескеАзе Кпу для каждого ребра. В плотных графах с большим количеством ребер амортизированное время выполнения Рнскнлзн Кет, равное 0(1), представляет собой существенный выигрыш по сравнению со временем 0(!бп) в наихудшем случае в биномиальных пирамидах. Быстрые алгоритмы для таких задач„как поиск минимального остовного дерева (глава 23) или поиск кратчайшего пути из одной вершины (глава 24), преимущественно опираются на фибоначчиевы пирамиды.
Однако с практической точки зрения программная сложность реализации и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых пирамид, делая их для большинства приложений менее привлекательными, чем обычные бинарные (или Й- арные) пирамиды.
Таким образом, интерес к фибоначчиевым пирамидам в первую очередь сугубо теоретический. Широкое практическое использование могла бы Глава 20. Фибоиаччиевы пирамиды 559 получить более простая структура данных, но обладающая тем же амортизированным временем работы, что и фибоначчиевы пирамиды. Подобно биномиальным пирамидам, фибоначчиевы пирамиды представляют собой набор деревьев. В действительности фибоначчиевы пирамиды в определенной степени связаны с биномиальными пирамидами. Если над фибоначчиевой пирамидой не выполняются процедуры Рескелзе Кеу и Ре~.его, то каждое дерево в пирамиде выглядит как биномиальное. Фибоначчиевы пирамиды имеют более слабую структуру, чем биномиальные пирамиды, что обеспечивает улучшенные асимптотические границы времени работы. Поддержка строгой структуры фибоначчиевы пирамиды в результате может быть отложена до того момента, когда выполнение соответствующих действий окажется более удобным.
Подобно динамическим таблицам из раздела 17.4, фибоначчиевы пирамиды представляют собой хороший пример структуры данных, разработанной с учетом применения амортизационного анализа. Материал данной главы предполагает, что вы ознакомились с главой 19, в которой рассматриваются биномиальные пирамиды. Дело в том, что наше представление структуры фибоначчиевых пирамид основано на структуре биномиальных пирамид, а некоторые операции, выполняемые над фибоначчиевыми пирамидами, аналогичны операциям над биномиальными пирамидами. Так же, как и биномиальные пирамиды, фибоначчиевы пирамиды не способны обеспечить эффективную поддержку процедуры поиска бпАксн, поэтому в процедуры в качестве параметра передается не ключ, а указатель на узел. При использовании фибоначчиевых пирамид в приложении, мы часто храним в каждом элементе пирамиды дескриптор соответствующего объекта приложения, так же как и каждый объект приложения хранит дескриптор соответствующего элемента пирамиды.
В разделе 20.1 дается определение фибоначчиевых пирамид, рассматривается их представление и потенциальная функция, используемая в амортизационном анализе. В разделе 20.2 показано, как реализовать операции сливаемых пирамид, получив при этом амортизированное время работы, показанное в табл. 19.1. Остальные операции, а именно Респплзп Ки' и Пн.птц, рассматриваются в разделе 20.3. И наконец, раздел 20.4 завершает анализ фибоначчиевых пирамид, а также поясняет, почему они так называются.
20.1 Структура фибоначчиевых пирамид Так же, как и биномиальная пирамида, фибоначчиева пирамида (г1Ьопасс1 Ьеар) представляет собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Однако в случае фибоначчиевых пирамид деревья Часть Ч. Сложные структуры данных Рис. 20.1. Пример фибоначчиевой пирамиды с шггью деревьями и 14 узлами не обязательно должны быть биномиальными. На рис. 20.1а приведен пример фибоначчиевой пирамиды. В отличие от деревьев в биномиальных пирамидах, где они упорядочены, деревья в фибоначчиевых пирамидах являются неупорядоченными деревьями с корнем.
Как показано на рис. 20.1б, каждый узел х содержит указатель р [х] на родительский узел и указатель сй1!И [х] на один из дочерних узлов. Дочерние узлы х объединены в один циклический дважды связанный список, который мы назовем слискам дочерних узлов (с)г116 Изг) х. Каждый дочерний узел р в списке дочерних узлов имеет указатели 1е1т [р] и г1дЫ [д], которые указывают на его левый и правый сестринские узлы соответственно. Если узел р является единственгпам дочерним узлом, то 1еГг [д] = г1дМ [у] = р. Порядок размещения узлов в списке дочерних узлов произволен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
