\Section{Применение модифицированной кучи Фибоначчи}{18 декабря}{Илья Кайсин}

\Subsection{Применение в алгоритме Дейкстры непосредственно}

Алгоритм Дейкстры, как известно, работает за время $\O(E \cdot \t{DecreaseKey} + V \cdot \t{ExtractMin})$. Модифицированная куча Фибоначчи позволяет делать операцию $\t{ExtractMin}$ не за $\O(\log V)$, а за $\O(\log C)$, где $C$ --- количество различных ключей, находящихся в данный момент в куче. 

Но если веса рёбер в графе --- целые числа от $1$ до $C$, то в алгоритме Дейкстры в куче будет как раз таки не более $C + 1$ различных ключей в каждый момент времени (просто потому что в момент релаксации вдоль ребра веса не больше $C$ мы не получим ключа, превосходящего минимальный более, чем на $C$). 

Таким образом, мы добились асимптотики $\O(E + V \log C)$.

\Subsection{Применение в Two-Level Radix Heap}

Two-Level Radix Heap без модификаций работает за время $\O(n(\log_t C + t))$, где $\log_t C$ берётся из поиска непустого бакета, а $t$ --- из поиска непустого подбакета. Если искать непустой подбакет с помощью модифицированной кучи Фибоначчи, можно получить время $\O(n(\log_t C + \log t))$. Асимптотического минимума функция достигает, когда $\log t = \sqrt{\log C}$, при этом получаем $\O(n \sqrt{\log C})$. 

Для того, чтобы $\t{ExtractMin}$ работал за $\sqrt{\log C}$, нужно удалять все вершины найденного подбакета разом. Добиться этого можно, если в куче Фибоначчи весу вершины будет соответствовать индекс подбакета, тогда нужно просто сделать в куче $\t{ExtractMin}$ (не $\t{ExtractMin}^*$). Но в этом случае нарушается потенциал, введённый при доказательстве времени работы модифицированной кучи Фибоначчи. Тем не менее, утверждается, что на асимтотику это не повлияет (доказательство остаётся читателям в качестве упражнения).

Таким образом, получили Дейкстру за $\O(E + V \sqrt {\log C})$.