|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[137] фибоначчиевы деревья обладают большей гибкостью, чем биномиальные (из них можно удалять некоторые вершины, откладывая перестройку дерева до удобного случая). Как и динамические таблицы раздела 18.4, фибоначчиевы кучи являются примером структуры данных, разработанной с учётом амортизационного анализа (см. гл. 18, особенно разд. 18.3 о методе потенциала). Мы предполагаем, что вы прочли предыдущую главу (о биномиальных кучах). Там была приведена таблица (рис. 20.1), где указаны оценки времени работы различных операций с биномиальными и фибоначчиевыми кучами. Как и биномиальные кучи, фибоначчиевы кучи не обеспечивают эффективного выполнения поиска (Search). Поэтому передавая вершину в качестве параметра, мы указываем не ключ вершины, а указатель на неё. В разделе 21.1 мы определим фибоначчиевы кучи, обсудим их представление в программе и введём потенциальную функцию. В разделе 21.2 мы покажем, как реализовать операции, присущие сливаемым кучам, с оценками учётной стоимости, указанными в таблице (рис. 20.1). Оставшиеся две операции (Decrease-Key и Delete) описаны в разделе 21.3. Наконец, в разделе 21.4 мы доказываем лемму, использованную при анализе построенных процеДУР- 21.1. Строение фибоначчиевой кучи При использовании фибоначчиевых куч для хранения набора множеств каждое множество занимает несколько деревьев, корни которых связаны в список. Такой конгломерат мы будем называть фибоначчиевой кучей (Fibonacci heap). Таким образом, каждая фи-боначчиева куча состоит из нескольких деревьев; для каждого хранимого множества отводится своя куча. В каждом из деревьев, входящих в кучу, выполнено такое свойство: ключ каждой вершины не больше ключей её детей. Деревья, однако, более не обязаны быть биномиальными. Пример фибоначчиевой кучи приведён на рис. 21.1а. В биномиальных деревьях на детях любой вершины фиксирован порядок; в фибоначчиевых деревьях такого порядка нет (дети любой вершины связаны в круговой двусторонний список, но порядок в нём несуществен). Как показано на рис. 21.16, каждая вершина х содержит указатель р[х] на своего родителя и указатель child[x] на какого-нибудь из своих детей. Дети вершины х связаны в двусторонний циклический список, называемый списком детей (child list) вершины х. Каждая верши- Рис. 21.1 (а) Фибоначчиева куча, содержащая 5 деревьев и 14 вершин. Пунктирной линией показан корневой список. Минимальная вершина содержит ключ 3. Три отмеченные вершины выделены чёрным цветом. Потенциал этой кучи равен 5 + 2-3 = 11. (б) Та же куча вместе со стрелками, показывающими значения полей р (стрелки вверх), child (стрелки вниз) и left и right (стрелки в стороны). На остальных рисунках этой главы такие стрелки опущены, так как они восстанавливаются однозначно. на у этого списка имеет поля left[y] и right[y], указывающие на её соседей в списке (левого и правого). Если вершина у является единственным ребёнком своего родителя, то left[y] = right[y] = у. Двусторонние циклические списки (см. разд. 11.2) удобны по двум причинам. Во-первых, из такого списка можно удалить любую вершину за время 0(1). Во-вторых, два таких списка можно соединить в один за время 0(1). Помимо указанной информации, каждая вершина имеет поле degree[x], где хранится её степень (число детей), а также поле тагк[х]. В этом поле хранится булевское значение. Смысл его таков: тагк[х] истинно, если вершина х потеряла ребёнка после того, как она в последний раз сделалась чьим-либо потомком. Мы объясним позже, как и когда это поле используется. Корни деревьев, составляющих фибоначчиеву кучу, связаны с помощью указателей left и right в двусторонний циклический список, называемый корневым списком (root list). Доступ к фибоначчиевой куче Н осуществляется с помощью атрибута min[H], который указывает на вершину корневого списка с минимальным ключом. Эта вершина называется минимальной вершиной (minimum node) кучи. Её ключ будет минимальным ключом в куче, поскольку минимальный ключ фибоначчиева дерева находится в его корне. Порядок вершин в корневом списке значения не имеет. Если фибоначчиева куча Н пуста, то тгп[Н] = nil. Наконец, атрибут п[Н] содержит число вершин в куче Н. Потенциал При анализе учётной стоимости операций мы используем метод потенциала (раздел 18.3). Пусть t(H) - число деревьев в корневом списке кучи Н, а т(Н) - количество отмеченных вершин. Потенциал определяется формулой Ф(Н) = Ь{Н) + 2т{Н).(21.1) Например, потенциал кучи рис. 21.1 равен 5 + 2-3 = 11. В каждый момент времени в памяти хранится несколько куч; общий потенциал по определению равен сумме потенциалов всех этих куч. В дальнейшем мы выберем «единицу измерения потенциала» так, чтобы единичного изменения потенциала хватало для оплаты 0(1) операций (формально говоря, мы умножим потенциал на подходящую константу). В начальном состоянии нет ни одной кучи, и потенциал равен 0. Как и положено (см. разд. 18.3), потенциал всегда неотрицателен. Максимальная степень Мы будем предполагать известной некоторую верхнюю границу D(n) для степеней вершин в кучах, которые могут появиться при выполнении наших процедур. (Аргументом функции D является общее число всех вершин в куче, обозначаемое через п.) Если мы используем только операции, предусмотренные для сливаемых куч, то можно положить D(n) = [lgn\ (упр. 21.2-3). В разделе 21.3 мы докажем (для общего случая, когда разрешены также операции Decrease-Key и Delete), что D(n) = O(lgra). 21.2. Операции, предусмотренные для сливаемых куч Для начала мы будем рассматривать лишь операции Маке-Heap, Insert, Minimum, Extract-Min и Union, предусмотренные для сливаемых куч. В этом случае кучи будут представлять собой набор «неупорядоченных биномиальных деревьев», корни которых связаны в циклический список. Неупорядоченное биномиальное дерево (unordered binomial tree) получается из упорядоченного, если мы перестаём обращать внимание на порядок среди вершин, имеющих общего родителя. Другими словами, неупорядоченное биномиальное дерево Uo состоит из единственной вершины, а неупорядоченное биномиальное |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||