\Section{Модификация Фибоначчевой кучи}{18 декабря}{Валерий Черепанов}
    
    \Subsection{Структура}
    Фибоначчева куча работает быстро. Add и DecreaseKey работают за $\O(1)$, а ExtractMin работает за $\O(\log n)$. Казалось бы, что лучшего и желать нельзя, но все-таки Фибоначчеву кучу можно ускорить, делая ExtractMin за $\O(\log c)$, где $c$ "--- количество различных весов в куче.

    Как же это сделать? Во-первых, вершины кучи будут парами $(w, \text{list}_w)$, где $w$ "--- это вес, а $\text{list}_w$ "--- множество id веса $w$, хранимое в виде списка (пример: при написании алгоритма Дейкстры в куче будут хранится пары $(\text{dist}[v], \{v\colon \text{dist}[v] == w\})$). Во-вторых, будем поддерживать массивы HeapNode (HeapNode[$w$] хранит указатель на вершину веса $w$) и ListNode (ListNode[id] хранит указатель на id в каком-то $\text{list}_w$).

    \Subsection{Операции}
    Напишем теперь новые операции для нашей новой кучи (они, в отличие от обычных операции Фибоначчевой кучи, будут отмечатся звездочкой). Для простоты будем считать, что все нужные массивы пересчитываются сами собой (на практике пересчет не должен вызвать проблем) и использовать только массив count, который хранит количество id данного веса.

    \Subsubsection{Add*}
    \begin{lstlisting}
    Add*(id, w):
        if count[w] > 0:
            count[w] += 1
        else:
            Add(id, w)
    \end{lstlisting}

    \Subsubsection{DecreaseKey*}
    \begin{lstlisting}
    DecreaseKey*(id, oldW, newW):
        if count[oldW] > 1:
            --count[oldW]
            Add*(id, newW)
        else:
            if count[newW] == 0: // Do not create or delete any nodes
                DecreaseKey(oldW, newW)
                swap(count[oldW], count[newW])
            else:
                count[oldW] = 0
                ++count[newW]
    \end{lstlisting}

    \Subsubsection{ExtractMin*}
    \begin{lstlisting}
    ExtractMin*():
        while True:
            w = GetMin()
            if count[w] > 0:
                break
            ExtractMin(); // Spend 1 coin
        if count[w] > 0:
            --count[w]
        else:
            ExtractMin(); // Spend 1 coin
        // Borrow 2 coins
    \end{lstlisting}

    \Subsection{Доказательство}
    Легко понять, что новые операции корректны, осталось понять, почему куча стала работать быстрее, то есть доказать, что ExtractMin* работает за $\O(\log c)$.

    Воспользуемся методом банковского учета. Обозначим количество монет буквой $\phi$ (изначально $\phi = 0$). Пусть каждая монета стоит $\log c$. При каждом запуске ExtractMin* мы берем две монеты, а на каждый вызов ExtractMin тратим одну монету.
    
    Нужно доказать, что монет всегда хватает, когда они тратятся, то есть $\phi \geq 0$.

    В момент появления в куче вершины веса $w$ отметим $e=\text{list}_w[0]$. Понятно, что $e$ будет удален раньше самой вершины. В момент удаления $e$ возьмем монету, которую потратим в момент удаления вершины.
    
%    По-моему это объяснение слишком длинное и только усложняет понимание.
%    Для этого введем понятие ``убийца''. Убийца $w$ "--- любой id, удаленный из $\text{list}_w$, который на момент удаления не был убийцей.
%    Заметим, что перед тем, как $\text{list}_w$ станет пустым, из кучи будет удален убийца $w$. То есть, перед тем как мы потратим монету на ExtractMin пустого элемента, мы получим ее за ExtractMin* убийцы.
%    
%    Проблемы могут возникнуть только в том случае, если у двух разных $w$ был один и тот же убийца. Докажем, что так быть не может.
%
%    Изначально убийц вообще не было, значит все было хорошо. Посмотрим, что происходит при выполнении операций:
%    \begin{enumerate}
%        \item Add* вообще никак не влияет на убийц.
%        \item ExtractMin* при удалении пустых элементов не добавляет убийства. При удалении из вершины кучи убийца может появится у нее, 
%    \end{enumerate}
%    
%    \Subsubsection{DecreaseKey*}
%    В случае, когда count[oldW] был равен одному, а элемент веса newW существовал и был не пуст, у oldW мог появится убийца. Рассмотрим 2 случая:
%    \begin{enumerate}
%        \item В $\text{list}_\text{oldW}$ остались не только убийцы. Тогда все хорошо, ведь перед тем, как список станет пуст, мы еще обновим убийцу.
%        \item В $\text{list}_\text{oldW}$ остались только убийцы. Тогда у oldW уже есть убийца, ведь по определению "--- это последний id, который не был убийцей на момент удаления, а он когда-то точно был.
%    \end{enumerate}

