работа по дисциплине «Технологии программирования» на тему: «Фибоначчиевы кучи» (стр. 2 из 4)
Максимальная степень Через
обозначим верхнюю границу для степеней узлов в кучах, которые могут появиться при выполнении операций. Аргументом функции 
является общее число всех узлов в куче, обозначаемое через 
.Мы не будем углубляться в анализ трудоемкости операций с фибоначчиевыми кучами, отсылая читателя к соответствующей литературе, скажем только, что
и все операции, кроме операции удаления элемента, имеют амортизационную трудоемкость 
, а операция удаления — 
.Впоследствии Д.Дрисколл и Р.Тарьян разработали структуру данных, называемую
, как замену для фибоначчиевых куч. Есть две разновидности такой структуры данных. Одна из них дает те же оценки учетной стоимости, что и фибоначчиевы кучи. Другая — позволяет выполнять операцию 
за время в худшем случае, а операции 
и Delete — за время 
в худшем случае. Эта структура данных имеет также некоторые преимущества по сравнению с фибоначчиевыми кучами при использовании в параллельных алгоритмах.Фибоначчиева куча является структурой данных для хранения данных позволяющей быстро производить следующие операции: добавление элемента, получение минимального элемента, удаление минимального элемента, уменьшение ключа по ссылке и удаление по ссылке. Данная структура организована следующим образам:
1. Существует явная ссылка на минимальный элемент.
2. У каждой вершины есть ссылка на правый и левый элемент в двусвязном списке содержащим эту вершину.
3. У каждой вершины есть ссылка child указывающая на одну из вершин спика ее детей.
4. У каждой вершины есть ссылка parent указывающая на родителя.
5. У каждой вершины есть булевское поле marked использующаяся при уменьшение ключа (см. ниже). Оно истинно если вершина потеряла ребенка после того как сделалась чьим-нибудь ребенком.
6. Список содержащей минимальную вершину называется корневым списком и родители всех его вершин отсутствуют.
Рассмотрим теперь реализуемые алгоритмы по отдельности.
1.5. Добавление элемента
Добавим нашу вершину в корневой список. Если окажется, что значение её ключа меньше минимального, то она становиться новой минимальной вершиной.
Создание пустой кучи
Ссылка minElement зануляется.
Удаление минимального элемента
Удаление минимального элемента состоит из двух частей. Сначала мы удаляем минимальную вершину из кучи, а всех ее детей добляем в корневой список. После этого мы объединяем вершины из корневого списка в вершины большей степени. Для этого мы создаем массив ссылок на элементы нашей кучи (индекс соответствует степени вершины). Просмотрим все вершины корневого списка занося их в массив, если окажется, что тот элемент, куда мы хотим занести нашу вершину, уже занят, то мы объединим эти две вершины в одну большей степени, сделав вершину с большим ключом ребенком вершины с меньшим ключом. Получившуюся вершину попробуем опять занести в массив и т. д. После добавим все вершины из массива в корневой спиок, находя паралельно минимум.
Уменьшение ключа
Данный алгоритм делится на два случая:
1. Новый ключ вершины больше ключа родителя. Тогда достаточно уменьшить ключ вершины до нового значения.
2. Новый ключ вершины меньше ключа родителя. Тогда перенесем нашу вершину в корневой список. После этого рассмотрим цепочку предков нашей вершины (её родитель, родитель ее родителя и т. д.). Найдем в этой цепочке первую неотмеченную вершину. Все вершины до нее переместим в корневой список, а ее отметим.
Удаление вершины
Для удаление вершины сначала уменьшим ее значение до «минус бесконечности», а потом удалим минимальную вершину.
1.6. Время выполнения различных операций для трёх видов сливаемых куч (n – общее число элементов в кучах на момент операции).
| Процедура | Двоичные кучи | Биномиальные кучи | Фибоначчиевы кучи |
| Создание | Q(1) | Q(1) | Q(1) |
| Вставка | Q(log n) | O(log n) | Q(1) |
| Найти мин. | Q(1) | O(log n) | Q(1) |
| Удалить мин. | Q(log n) | Q(log n) | O(log n) |
| Слить | Q(n) | O(log n) | Q(1) |
| Уменьшить ключ | Q(log n) | Q(log n) | Q(1) |
| Удалить | Q(log n) | Q(log n) | O(log n) |
1.7. Оценки времени работы
Сводная таблица амортизированного времени работы:
| Операция | Binary | Leftist | Top-Down Skew | Bottom-Up Skew | Pairing | Binomial | Fibonacci | 2-3 | Soft |
| MAKE | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
| INSERT | O(log N) | O(log N) | O(log N) | O(1) | O(log N) * | O(log N) | O(1) | O(1) | O(log 1/E) |
| MELD | O(N) | O(log N) | O(log N) | O(1) | O(log N) * | O(log N) | O(1) | O(log N) | O(1) |
| FIND-MIN | O(1) | O(1) | O(1) | O(1) | O(1) | O(log N) | O(1) | O(1) | O(1) |
| DELETE-MIN | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) | O(1) |
| DECREASE | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) * | O(log N) | O(1) | O(1) | O(1) |
| DELETE | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) | O(log N) | O(1) |
* Для Pairing куч операции добавления элемента, уменьшения ключа и слияния гипотетически выполняются за время O(1), но данная оценка еще не доказана.
Глава II. Пример реализации алгоритма Дейкстры в среде Delphi
2.1. Алгоритм Дейкстры
Алгори́тм Де́йкстры — алгоритм на графах , изобретенный Э. Дейкстрой . Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Неформальное определение.
Вариант 1. Дана сеть автомобильных дорог, соединяющих города Львовской области. Найти кратчайшие расстояния от Львова до каждого города области (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Найти минимальную стоимость маршрута (возможно, с пересадками) от Копенгагена до Новосибирска .
Вариант 3. Есть план города с нанесёнными на него местами расположения пожарных частей. Определить ближайшую к каждому дому пожарную станцию.
Формальное определение.
Дан простой взвешенный граф G ( V , E ) без петель и дуг отрицательного веса. Найти кратчайшее расстояние от некоторой вершины a графа G до всех остальных вершин этого графа.
Неформальное определение.
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a . Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация . Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Шаг алгоритма . Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u , имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.