|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[141] Сит(Я,ж,у) 1удалить х из списка детей вершины у, уменьшив degree[y] на 1 2добавить х в корневой список кучи Н 3р[х] <- nil 4mark[x] <- false Cascading-Cut(#, у) 1z <r- p[y] 2if z ф nil 3then if mark[y] = false 4then mark[y] <- true 5else Сит(Я, y,z) 6Cascading-Cut(#, z) Процедура Fib-Heap-Decrease-Key работает так. Сначала (строки 1-3) проверяется, действительно ли новое значение ключа меньше старого. Если да, то старое значение заменяется на новое. Возможно, новое значение по-прежнему больше значения в вершине-родителе, тогда всё в порядке. Если же нет, то в строках 6-7 поддерево с корнем х вырезается и переносится в корневой список с помощью процедур «каскадного вырезания». Идея тут проста: мы не хотим позволять вершине всплывать до корня (напомним: нам нужна оценка 0(1) для учётной стоимости). Приходится её вырезать целиком и помещать в корневой список. От этого растёт потенциал, но всего на 0(1), так что это не страшно. Но мы должны следить за структурой дерева, поскольку хотим иметь логарифмическую оценку на максимальную степень вершины (D(n) = O(lgra)). Забегая вперёд, отметим, что высота дерева не обязана быть логарифмической (см. упр. 21.4-1). Мы будем следить, чтобы у одной и той же вершины, не входящей в корневой список, не удалялось несколько детей. Для этого используются пометки (поле mark): после удаления ребёнка (перенесения его в корневой список с помощью процедуры Сит) вершина делается отмеченной, если она ранее не была отмеченной и не была корнем (строки 3-4 процедуры Cascading-Cut). Если же вершина, у которой удалён ребёнок, уже была отмеченной, то она сама переносится в корневой список, а для её родителя повторяется та же процедура. После выполнения операций вырезания остаётся только скорректировать атрибут тгп[Н]. Заметим, что минимальной может быть либо вершина с уменьшенным ключом, либо прежняя минимальная вершина. Таким образом, жизненный цикл вершины выглядит так. Сначала она добавляется в дерево, попадая в его корневой список. При выполнении операции Consolidate деревья в корневом спис- ке объединяются. При этом вершина может либо остаться в корневом списке, приобретя нового ребёнка (если её ключ меньше ключа другой вершины, с которой она объединяется), либо стать ребёнком другой вершины корневого списка. Вершина корневого списка может не только приобретать детей, но и терять их (процедура Сит); отметим, что при этом она не становится помеченной (строка 4 процедуры Cascading-Cut выполняется, лишь если выполнено условие в строке 2). В какой-то момент вершина исключается из корневого списка, становясь ребёнком другой вершины при выполнении процедуры Consolidate. При этом её пометка (если она была) удаляется (строка 3 процедуры Fib-Link). С этого момента новых детей у неё не прибавляется, но может быть удалён один ребёнок, отчего она станет помеченной. При удалении второго ребёнка вершина вновь перемещается в корневой список, становясь непомеченной. Другой способ вернуться в корневой список - оказаться ребёнком изымаемой вершины при операции Fib-Heap-Extract-Min (при этом пометка не меняется). После возвращения в корневой список к вершине вновь могут добавляться дети (при операции Consolidate). Дети могут и удаляться (операция Сит). В какой-то момент вершина снова может оказаться ребёнком другой вершины корневого списка, и так далее - до тех пор, пока эта вершина не будет изъята из дерева (или не будет уменьшен ключ). На рис. 21.4 показаны две операции Fib-Heap-Decrease-Key, первая из которых не вызывает цепочки операций Сит, а вторая вызывает. Покажем, что учётная стоимость операции Fib-Heap-Decrease-Key составляет 0(1). Начнем с определения фактической стоимости. Процедуры Fib-Heap-Decrease-Key, Сит и Cascading-Cut не содержат циклов, так что время работы пропорционально длине цепочки рекурсивных вызовов (которую мы обозначим через с). Как при этом меняется потенциал? Цепочка рекурсивных вызовов соответствует цепочке помеченных вершин в дереве, каждая из которых является ребёнком следующей. Эти вершины перемещаются в корневой список и становятся непомеченными. Таким образом, потенциал увеличивается примерно на с за счёт увеличения числа вершин в корневом списке, но и уменьшается примерно на 2с за счёт того, что уменьшается число помеченных вершин. (Правда, может появиться новая помеченная вершина, но эта поправка имеет порядок 0(1).) В итоге потенциал уменьшается на с + 0(1). (Теперь ясно, почему при определении потенциала число помеченных вершин учитывалось со вдвое большим весом, чем число вершин в корневом списке!) Умножая потенциал на достаточную константу (выбирая боль- Рис. 21.4 Два вызова процедуры Fib-Heap-Decrease-Key. (а) Исходная фибоначчиева куча, (б) Ключ 46 уменьшается до 15, соответствующая вершина становится корневой, а её родитель (с ключом 24) - отмеченным, (в)-(д) Ключ 35 уменьшается до 5; вершина стала корневой (в). Её родитель (с ключом 26) был отмечен, так что его приходится также перенести в корневой список (г); затем то же самое происходит и с ключом 24. На этом каскад вырезаний заканчивается, так как вершина с ключом 7 - корневая. (Если бы она не была корневой, то она стала бы отмеченной, и каскад всё равно закончился бы.) После этого остаётся перенести указатель тгп[Н] на новую минимальную вершину (д). шую «единицу работы»), можно считать, что уменьшение потенциала компенсирует фактическую стоимость цепочки рекурсивных вызовов, так что учётная стоимость операции Fib-Heap-Decrease-Key есть 0(1). Удаление вершины Эта операция сводится к двум рассмотренным ранее (мы считаем, что ключ -оо меньше всех ключей кучи). Fib-Heap-Delete (Я, ж) 1Fib-Heap-Decrease-Key(#, ж, -оо) 2Fib-Heap-Extract-Min(#) Аналогичным образом мы поступали и с биномиальными деревьями. Сначала вершина ж делается минимальной, а затем удаляется. Учётная стоимость таких действий равна сумме учётной сто- |
Среды: 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 | ||