Фибоначчиева куча
Содержание
Фибоначчиево дерево
Определение: |
Фибоначчиево дерево — биномиальное дерево, где у каждой вершины удалено не более одного ребенка. |
Определение: |
Порядок фибоначчиева дерева — порядок соответствующего биномиального дерева, из которого оно получено. |
Лемма: |
Для всех целых
, где — -ое число Фибоначчи, определяемое формулой: |
Доказательство: |
Докажем лемму по индукции: при , что действительно верно. По индукции предполагаем, что . Тогда |
Лемма: |
Фибоначчиево дерево порядка содержит не менее вершин. |
Доказательство: |
Докажем это утверждение по индукции. Пусть — минимальный размер фибоначчиева дерева порядка n.При . При . Предположим по индукции, что для всех . Пусть в нашем дереве удалено поддерево порядка . ТогдаНо по предыдущей лемме . Следовательно, |
Фибоначчиева куча
Определение: |
Фибоначчиева куча — набор фибоначчиевых деревьев, упорядоченных в соответствии со свойством неубывающей кучи. |
Фибоначчиевы кучи поддерживают тот же набор операций, что и биномиальные кучи, но имеют то преимущество, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное .
С теоретической точки зрения фибоначчиевы кучи особенно полезны в случае, когда количество операций бинарные кучи.
и относительно мало по сравнению с количеством других операций. Однако с практической точки зрения программная сложность и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых куч, делая их в большинстве случаев менее привлекательными, чем обычные
Определение: |
Степень вершины — порядок фибоначчиева дерева, чьим корнем эта вершина является. |
Лемма: |
, где |
Доказательство: |
Для начала докажем, что Используем для этого математическую индукцию. При , что верно. При , что также верно. По индукции предполагаем, что и . Тогда
Подставив вместо Поскольку его значение, нетрудно убедится, что , то выполняются неравенства . Таким образом, -ое число Фибоначчи равно , округленному до ближайшего целого числа. Следовательно, . |
Лемма: |
Максимальная степень произвольной вершины в фибоначчиевой куче с вершинами равна |
Доказательство: |
Пусть доказанному выше в дереве, корень которого , содержится не менее вершин, что в свою очередь по лемме равно . То есть — произвольная вершина в фибоначчиевой куче с вершинами, и пусть — степень вершины . Тогда по
Логарифмируя по основанию , получаемТаким образом, максимальная степень произвольной вершины равна . |
Структура
- Каждый узел
- — поле, в котором хранится ключ;
- — указатель на родительский узел;
- — указатель на один из дочерних узлов;
- — указатель на левый сестринский узел;
- — указатель на правый сестринский узел;
- — поле, в котором хранится количество дочерних узлов;
- — логическое значение, которое указывает, были ли потери узлом дочерних узлов, начиная с момента, когда стал дочерним узлом какого-то другого узла.
в куче содержит следующие указатели и поля:
- Дочерние узлы циклический двусвязный список. объединены при помощи указателей и в
- Корни всех деревьев в циклический двусвязный список корней. связаны при помощи указателей и в
- Обращение к выполняется посредством указателя на корень дерева с минимальным ключом. Этот узел называется минимальным узлом .
- Текущее количество узлов в хранится в .
Циклический двусвязный список обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время . Во-вторых, если имеется два таких списка, их легко объединить в один за время .
Потенциал
Для анализа производительности операций введем потенциал для фибоначчиевой кучи
как , где — количество элементов в корневом списке кучи, а — количество вершин, у которых удален один ребенок (то есть вершин с пометкой ). Договоримся, что единицы потенциала достаточно для оплаты константного количества работы. На языке метода предоплаты это выглядит следующим образом: возле каждого корня лежит одна монета, а возле каждой вершины, у которой удалили ребенка, лежит две монеты.Операции
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции и получают в качестве аргумента указатель на узел, а не значение его ключа.
makeHeap
Создается новый пустой корневой список, в
устанавливается значение . Реальное время работы — .insert
Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость операции: 1 (создание кучи) + 2 (слияние куч + релаксация минимума) + 1(изменение потенциала) = 4 =
.getMin
Возвращает указатель
. Реальное время работы —merge
Слияние двух фибоначчиевых куч происходит просто: объединяем списки этих куч в один, релаксируем минимум. Реальное время работы —
. Амортизированное время работы также , поскольку, при объединении двух куч в одну, потенциалы обеих куч суммируются, итоговая сумма потенциалов не изменяется, .extractMin
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура лемме .
. Возьмем указатель на , удалим эту вершину. Ее поддеревья (их не более, чем , где — максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру . После этой операции в списке корней остается не более чем узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции , учитывая и вспомогательную функцию , время работы которой доказывается ниже, равно: . По доказанной вышеconsolidate
Данная процедура принимает кучу и преобразует ее таким образом, что в корневом списке остается не более
вершин.Для этого возьмем массив списков указателей на корни деревьев
, где — максимальная степень вершины в текущем корневом списке.Затем происходит процесс, аналогичный слиянию биномиальных куч: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна . Если в соответствующей ячейке еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна . Продолжаем, пока не найдем свободную ячейку.
Учетная стоимость
равна . Докажем это:Изначально в корневом списке было не более
вершин, поскольку он состоит из исходного списка корней с узлами, минус извлеченный узел и плюс дочерние узлы, количество которых не превышает . В ходе операции мы сделали слияний деревьев. Потенциал перед извлечением минимума равен , а после не превышает , поскольку в корневом списке остается не более узлов, а количество помеченных узлов не изменяется. Таким образом, амортизированная стоимость не превосходит
Поскольку мы договорились, что можем масштабировать единицу потенциала таким образом, чтобы покрывать константное количество работы, то итоговая амортизационная оценка —
decreaseKey
Основная идея: хотим, чтобы учетная стоимость данной операции была
. Было бы хорошо, чтобы вершина не всплывала до корня, и тогда дерево не придется сильно перестраивать. Для этого при удобном случае будем вырезать поддерево полностью и перемещать его в корневой список. Итак, сам алгоритм:- Проверяем, если новое значение ключа все же не меньше значения ключа родителя, то все хорошо, и мы выходим.
- Иначе, вырезаем дерево с текущей вершиной в корневой список, и производим каскадное вырезание родителя.
cut
При вырезании вершины мы удаляем ее из списка детей своего родителя, уменьшаем степень ее родителя (
) и снимаем пометку с текущей вершины ( ).cascadingCut
Перед вызовом каскадного вырезания нам известно, удаляли ли ребенка у этой вершины. Если у вершины до этого не удаляли дочерний узел (
), то мы помечаем эту вершину ( ) и прекращаем выполнение операции. В противном случае применяем операцию для текущей вершины и запускаем каскадное вырезание от родителя.Пример
Рисунок иллюстрирует пример каскадного вырезания:
- Изначально, куча состояла из 3 фибоначчиевых деревьев. У вершины с ключом 24 отсутствует 1 ребенок.
- Уменьшаем ключ 26 до 5 и делаем операцию этого дерева. Получаем кучу с 4 деревьями и новым минимумом. Но у вершины с ключом 24 был удален второй ребенок, поэтому запускам операцию для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.
- У вершины с ключом 7 удален лишь один ребенок, поэтому операция от нее не запускается. В итоге, получаем кучу, состоящую из 5 фибоначчиевых деревьев.
Время работы
Докажем, что амортизированное время работы операции
есть . Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.Пусть мы вызвали процедуру каскадного вырезания
раз. Тогда вершин с пометкой стало на меньше, а в корневом списке прибавилось новых вершин. Итого, время работы будет: . Следовательно, амортизированная стоимость не превышает , поскольку мы можем соответствующим образом масштабировать единицы потенциала.На языке метода предоплаты: пусть у каждого узла в списке корней лежит монета, а у каждой помеченной вершины — 2 монеты. Покажем, что взяв 4 монеты за операцию
, мы сможем оплатить эту операцию. Одну монету потратим на перенос в корневой список и релаксацию минимума, еще 1 — на то, чтобы положить монету у новой вершины в корневом списке, которую мы потратим на следующую операцию . У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда , кладем 2 монеты к этой вершине, и устанавливаем соответствующую пометку. Инвариант сохраняется.Иначе, добавляем к помеченной вершине родителя еще 2 монеты. В итоге, в родительском узле становится 4 монеты, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.
delete
Удаление вершины реализуется через уменьшение ее ключа до
и последующим извлечением минимума. Амортизированное время работы: .Поскольку ранее мы показали, что
, то соответствующие оценки доказаны.Источники
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ. — М.: Издательский дом «Вильямс», 2005. — С. 1296. — ISBN 5-8459-0857-4
- Числа Фибоначчи — Википедия
- Фибоначчиева куча — Википедия
- Фибоначчиевы кучи — INTUIT.ru
- Визуализаторы
- Fibonacci Heaps