\Section{Фибоначчиева куча}{12 котября}{Егор Щербин}

\Subsection{От биномиальных деревьев к фибоначчиевым}

В предыдущей части мы научились делать биномиальную кучу с \t{Add} и \t{Merge} за $\O(1)$ и \t{ExtractMin} за амортизированное $\O(\log n)$. Немного расширим наши представления о ней, чтобы суметь сделать и уменьшение ключа за константу.

\begin{Def}
    Неформально говоря, фибоначчиево дерево "--- обрезанное биномиальное дерево.

    Определим формально:
    \begin{itemize}
        \item
            Фибоначчиево дерево ранга $0$, $F_0$, "--- просто вершина.
        \item
            Фибоначчиево дерево ранга $n$, $F_n$ ($n>0$), "--- дерево, сыновьями корня которого являются $n$ или $n-1$ фибоначчиевых деревьев меньших рангов, причем все ранги сыновей попарно различны.
        \item
            Естественно, фибоначчиево дерево удовлетворяет свойству кучи.
    \end{itemize}
\end{Def}

\begin{Def}
    Фиббоначиева куча "--- список фибоначчиевых деревьев.
\end{Def}

В фибоначчиевом дереве дети вершины не обязательно упорядочены по рангу. Для того, чтобы в дальнейшем можно было удалять у вершины сына, будем хранить детей в двусвязном списке.

Все операции, кроме удаления и уменьшения ключа элемента, происходят в фибоначчиевой куче так же, как и в улучшенной биномиальной куче.

Пока нет уменьшения ключа, наша куча не отличается от биномиальной и работает за такое же время.

\Subsection{Буду резать, буду удалять...}

Добавим \t{DecreaseKey} за амортизированное $\O(1)$. Удаление выражается через него: уменьшим ключ удаляемого элемента до $-\infty$ и извлечем минимум.

Будем теперь каждую вершину помечать, если у нее недостает одного сына, то есть она имеет ранг $n$, но $n-1$ сыновей.

Тогда в \t{DecreaseKey($v$)} после непосредственного уменьшения ключа $v$ можно рассматривать следующие три случая:
\begin{enumerate}
    \item
        Если инвариант кучи не нарушен, то больше ничего не делаем.
    \item
        Иначе если отец $v$ не помечен, то можно ``вырезать'' $v$, то есть удалить её из списка детей отца $v$ и добавить в основной список деревьев кучи (так же, как в Pairing Heap). Теперь нужно пометить бывшего отца $v$.
    \item
        Если отец $v$ уже помечен, то все равно вырезаем $v$, а потом рекурсивно вырезаем отца $v$ (в результате чего, возможно, придется вырезать и дедушку $v$, и следующих предков). 
\end{enumerate}
В любом случае, у всех только что вырезанных вершин нужно снять пометки, если они там были.

Сейчас может создаться ощущение, что мы поломали всю структуру, ведь, строго говоря, после удаления хотя бы двух сыновей у корня дерева, оно больше не попадает под наше определение фибоначчиева дерева.

Улучшим ситуацию, немного переопределив понятие ранга фибоначчиева дерева.

\begin{Def}
    Ранг фибоначчиева дерева "--- степень его корня в последний момент времени, когда оно лежало в основном списке кучи.
\end{Def}

Чтобы такое определение было более интуитивным, рассмотрим дерево в тот момент, когда оно исчезает из списка корней кучи (т.е. подвешивается к дереву такого же ранга). 
Тогда до тех пор, пока оно опять не попадет в основной список, его степень будет не более, чем на $1$, меньше его ранга "--- а ведь именно это свойство и является одним из ключевых в фибоначчиевом дереве.

\Subsection{А причём тут, собственно, Фибоначчи?}

\begin{Lm}
    Пусть $Fib_n$ "--- $n$-е число Фибоначчи. Тогда $Fib_n=1+\sum\limits_{i=1}^{n-2}{Fib_n}$
    \proof
    Докажем по индукции:
    \begin{itemize}
        \item
            База: $Fib_0=Fib_1=1$.
        \item
            Переход: $Fib_n=Fib_{n-1}+Fib_{n-2}=1+\sum\limits_{i=1}^{n-3}{Fib_n}+Fib{n-2}=1+\sum\limits_{i=1}^{n-2}{Fib_n}$.
    \end{itemize}
\end{Lm}

\begin{Lm}
    В фибоначчиевой куче у фибоначчиева дерева ранга $n$, можно так упорядочить детей корня, что ранг $i$-го из них будет не меньше $i$.
    \proof
    Доказать это можно индукцией по количеству операций над кучей. База "--- пустая куча "--- очевидна. Переход:
    \begin{itemize}
        \item
            При добавлении одного элемента это свойство не нарушается, при слиянии двух куч "--- тем более.
        \item
            При вырезании $v$, если она у своего отца имела номер $i$ (в порядке, определённом условием леммы и существующем по предположению индукции), то у всех следующих сыновей отца $v$ неравенство только усилилось.
        \item
            При подвешивании одного дерева ранга $n$ к другому дереву такого же ранга мы можем сопоставить новому сыну номер $n$.
    \end{itemize}
\end{Lm}

\begin{Lm}
    В фибоначчиевой куче размер фибоначчиева дерева ранга $n$ не меньше $Fib_n$. 
    \proof
    Доказать это можно аналогичной индукцией по количеству операций над кучей. Рассмотрим дерево которое получилось в
    результате очередной операции.
    По предыдущей лемме, можно упорядочить детей его корня так, чтобы ранг $i$-го из них будет не меньше $i$, значит, по
    предположению индукции, размер $i$-го хотя бы $Fib_i$. Пусть размер всего дерева равен $S$, а размер $i$-го из сыновей "--- $S_i$. 
    Забудем теперь про $n$-го сына, если он есть, и оценим размер всего дерева:
    $S\geqslant1+\sum\limits_{i=0}^{n-2}{S_i}\geqslant1+\sum\limits_{i=0}^{n-2}{Fib_n}=Fib_n$.
\end{Lm}

\begin{Rem}
    В фибоначчиевой куче размер дерева ранга $n$ хотя бы $\varphi^n$, где $\varphi$ "--- золотое сечение.
\end{Rem}

\begin{Rem}
    Если куча содержит $n$ элементов и в списке кучи все деревья имеют различные ранги, то их количество "--- $\O(\log n)$.
\end{Rem}

Оценим, наконец, время работы всех операций. Для этого введем потенциал, равный $2M+R$, где $M$ "--- количество помеченных вершин, а $R$ "--- количество корней в списке кучи. Cразу заметим, что изначально он равен $0$, а после $n$ операций точно не больше $3n$.

Итак,
\begin{itemize}
    \item
        \t{Add}: Потенциал изменяется на $1$, как реальное, так и амортизированное время работы "--- $\O(1)$
    \item
        \t{Merge}: Потенциалы двух сливаемых куч складываются, тоже $\O(1)$.
    \item
        \t{ExtractMin}: $M$ не изменяется, поэтому значимым слагаемым в потенциале является только $R$. Имея его, аналогично биномиальной куче, амортизированное время работы "--- $\O(\log n)$.
    \item
        \t{DecreaseKey}: Пусть было вырезано $k$ вершин, тогда хотя бы у $k-1$ из них (кроме самой первой), снялась пометка. Количество помеченных вершин уменьшилось хотя бы на $k-1$, а количество корней увеличилось на $k$, поэтому изменение потенциала не больше $2(1-k)+k=2-k$. Так как реальное время работы "--- $k$, то амортизированное время работы "--- $\O(1)$.
\end{itemize}

\Subsection{Бонус: нужно больше сравнений!}

\begin{Thm}
    Любой корректный алгоритм построения бинарной кучи из $n$ элементов делает не менее $1.3644n$ сравнений.
    \proof
    Будем оценивать на перестановках чисел от $1$ до $n$.

    Посчитаем, сколько существует бинарных куч. Сначала есть множество из $n!$ перестановок. На первом шаге мы обмениваем минимальный элемент с элементом в корне. Видно, что перестановка $p$ могла получиться ровно из $n$ других, так как в исходной перестановке минимум мог лежат на любом из $n$ мест. 
    Значит количество перестановок в множестве уменьшилось в $n$ раз.

    На $i$-м шаге обмениваем элемент на $i$-м месте с минимумом $i$-й вершины. Аналогично, количество перестановок уменьшилось в $s_i$ раз, где $s_i$ "--- размер поддерева $i$-й вершины ($s\simeq n,\frac{n}2,\frac{n}4,\frac{n}4,\frac{n}4,\frac{n}4,\ldots$).

    В итоге получим множество всех корректных бинарных куч. Его размер равен $\dfrac{n!}{\prod\limits_{i=1}^{n}{s_i}}$.

    Теперь предположим, что алгоритм делает $k$ сравнений. Тогда перестановки разбиваются на $2^k$ групп, в одной группе к каждой перестановке применяется одна и та же последовательность обменов. Тогда существует группа размера хотя бы $\frac{n!}{2^k}$.
    Так как перестановки в ней различны, а последовательность обменов совпадает, все перестановки в ней превращаются в различные бинарные кучи. 
    Получается, что количество различных бинарных куч не меньше, чем размер этой группы, то есть:

    $\dfrac{n!}{\prod\limits_{i=1}^{n}{s_i}}\geqslant\dfrac{n!}{2^k}\Rightarrow2^k\geqslant\prod\limits_{i=1}^{n}{s_i}\Rightarrow k\geqslant1.3644n$

    Последний переход шёл без доказательства.

\end{Thm}
