Куча Фибоначчи
-
Структура кучи Фибоначчи
- Куча Фибоначчи состоит из набора упорядоченных деревьев, удовлетворяющих свойству минимальной кучи.
- Деревья не имеют заданной формы, что позволяет выполнять операции в отложенном режиме.
- Степень узлов ограничена логарифмом размера кучи, что улучшает амортизированное время выполнения.
-
Операции с кучей Фибоначчи
- Вставка и уменьшение ключа выполняются за постоянное время.
- Удаление минимального элемента занимает O(log n) амортизированное время.
- Объединение двух куч Фибоначчи также выполняется за постоянное время.
-
Анализ амортизированного времени
- Амортизированное время операций определяется с помощью потенциальной функции.
- Потенциал зависит от количества деревьев и отмеченных узлов.
- Амортизированное время операции равно сумме фактического времени и разницы в потенциале.
-
Операции и их сложность
- Операция find-min занимает O(1) время.
- Операция merge-min также выполняется за постоянное время.
- Операция insert-min также выполняется за постоянное время.
- Операция delete-min занимает O(log n) время.
-
Доказательство границ степеней
- Размер поддерева, укорененного в узле степени k, не менее Fk+2.
- Это достигается с помощью правила отсечения не более одного дочернего узла.
- Количество деревьев уменьшается при выполнении операции delete-min.
-
Золотое сечение и его применение
- Золотое сечение (φ) равно 1,618.
- n ≥ Fd + 2 ≥ φd.
- d ≤ logφn.
-
Определение размера узла в куче Фибоначчи
- Размер узла x определяется как число его потомков, включая x сам.
- Высота x (длина самого длинного пути от x к листу-потомку) ≥ Fd + 2.
-
Индуктивное доказательство
- Базовый случай: если x имеет высоту 0, то d = 0 и размер x = 1 ≥ F2.
- Индуктивный случай: если x имеет положительную высоту и степень d > 0, то c1 ≥ i-2 для каждого i.
- Размер yi ≥ Fci + 2 ≥ F(i-2) + 2 = Fi.
- Размер x ≥ 2 + ∑i=2d размер yi ≥ 2 + ∑i=0d Fi = Fd + 2.
-
Недостатки куч Фибоначчи
- Сложность реализации.
- Высокая стоимость памяти и постоянные коэффициенты.
- Не подходят для систем реального времени.
-
Альтернативные структуры данных
- Очередь Бродаля: сложная и неприменимая на практике.
- Строгая куча Фибоначчи: более простая, но медленнее, чем очередь Бродаля.
- Кучи с упрощенной обработкой Driscoll et al.: хорошая производительность в наихудшем случае, кроме слияния.
-
Экспериментальные результаты
- Куча Фибоначчи более эффективна, чем большинство производных, но менее эффективна, чем кучи пар или на основе массивов.
-
Временные сложности
- Различные структуры данных кучи имеют разные временные сложности.
- Аббревиатура am. указывает на амортизированную сложность.
- Названия операций предполагают минимальное количество операций.