chapter05.tex

\chapter{Основы амортизации}
\label{ch:5}

За последние пятнадцать лет амортизация стала мощным инструментом в
построении и анализе структур данных. Реализации с амортизированными
характеристиками производительности часто оказываются проще и быстрее,
чем реализации со сравнимыми жёсткими характеристиками. В этой главе
мы даем обзор основных методов амортизации и иллюстрируем эти идеи
через простую реализацию очередей FIFO и несколько реализаций кучи.

К сожалению, простой подход к амортизации, рассматриваемый в этой
главе, конфликтует с идеей устойчивости~--- эти структуры, будучи
используемы как устойчивые, могут быть весьма неэффективны. Однако на
практике многие приложения устойчивости не требуют, и часто для таких
приложений реализации, представленные в этой главе, могут быть
замечательным выбором. В следующей главе мы увидим, как можно
совместить понятия амортизации и устойчивости при помощи ленивого
вычисления.

\section{Методы амортизированного анализа}
\label{sc:5.1}

Понятие амортизации возникает из следующего наблюдения.  Имея
последовательность операций, мы можем интересоваться временем, которое
отнимает вся эта последовательность, однако при этом нам может быть
безразлично время каждой отдельной операции. Например, имея $n$
операций, мы можем желать, чтобы время всей последовательности было
ограничено показателем $O(n)$, не настаивая, чтобы каждая из этих
операций происходила за время $O(1)$. Нас может устраивать, чтобы
некоторые из операций занимали $O(\log n)$ или даже $O(n)$, при
условии, что общая стоимость всей последовательности будет
$O(n)$. Такая дополнительная степень свободы открывает широкое
пространство возможностей при проектировании, и часто позволяет найти
более простые и быстрые решения, чем варианты с аналогичными жёсткими
ограничениями.

Чтобы доказать, что соблюдается амортизированное ограничение, нужно
определить амортизированную стоимость для каждой операции, и доказать,
что для любой последовательности операций общая амортизированная
стоимость является верхней границей общей реальной стоимости, т.~е.,
$$
\sum_{i=1}^m a_i \ge \sum_{i=1}^m t_i
$$
где $a_i$~--- амортизированная стоимость операции $i$, $t_i$~--- ее
реальная стоимость, а $m$~--- общее число операций. Обычно
доказывается несколько более сильный результат: что на любой
промежуточной стадии в последовательности операций общая текущая
амортизированная стоимость является верхней границей для общей текущей
реальной стоимости, т.~е.,
$$
\sum_{i=1}^j a_i \ge \sum_{i=1}^j t_i
$$
для любого $j$. Разница между общей текущей амортизированной стоимостью
и общей текущей реальной стоимостью называется
\term{текущие накопления}{accumulated savings}. Таким образом, общая
текущая амортизированная стоимость является верхней границей для
общей текущей реальной стоимости тогда и только тогда, когда текущие
накопления неотрицательны.

Амортизация позволяет некоторым операциям быть дороже, чем их
амортизированная стоимость. Такие операции называются
\term{дорогими}{expensive}. Операции, для которых амортизированная
стоимость превышает реальную, называются
\term{дешевыми}{cheap}. Дорогие операции уменьшают текущие накопления,
а дешевые их увеличивают. Главное при доказательстве
амортизированных характеристик стоимости~--- показать, что дорогие
операции случаются только тогда, когда текущих накоплений хватает,
чтобы покрыть их дополнительную стоимость.

Тарьян \cite{Tarjan1985} описывает два метода для анализа
амортизированных структур данных: \term{метод банкира}{banker's
  method} и \term{метод физика}{physicist's method}. В методе банкира
текущие накопления представляются как \term{кредит}{credits},
привязанный к определенным ячейкам структуры данных. Этот кредит
используется, чтобы расплатиться за будущие операции доступа к этим
ячейкам.  Амортизированная стоимость операции определяется как ее
реальная стоимость плюс размер кредита, выделяемого этой операцией,
минус размер кредита, который она расходует, т.~е.,
$$
a_i = t_i + c_i - \bar{c}_i
$$
где $c_i$~--- размер кредита, выделяемого операцией $i$, а $\bar{c}_i$~---
размер кредита, расходуемого операцией $i$. Каждая единица кредита
должна быть выделена, прежде чем израсходована, и нельзя расходовать
кредит дважды. Таким образом, $\sum c_i \ge \sum \bar{c}_i$, а
следовательно, как и требуется, $\sum a_i \ge \sum t_i$. Как правило,
доказательства с использованием метода банкира определяют
\term{инвариант кредита}{credit invariant}, регулирующий распределение
кредита так, чтобы при всякой дорогой операции достаточное его
количество было выделено в нужных ячейках структуры для покрытия
стоимости операции.

В методе физика определяется функция $\Phi$, отображающая всякий
объект $d$ на действительное число, называемое его
\term{потенциалом}{potential}.  Потенциал обычно выбирается так, чтобы
изначально равняться нулю и оставаться неотрицательным. В таком случае
потенциал представляет нижнюю границу текущих накоплений.

Пусть объект $d_i$ будет результатом операции $i$ и аргументом
операции $i+1$. Тогда амортизированная стоимость операции $i$
определяется как сумма реальной стоимости и изменения потенциалов между
$d_{i-1}$ и $d_i$, т.~е.,
$$
a_i = t_i + \Phi(d_i) - \Phi(d_{i-1})
$$
Текущая реальная стоимость последовательности операций равна
$$
\begin{array}{rcl}
\sum_{i=1}^j t_i & = & \sum_{i=0}^j (a_i + \Phi(d_{i-1}) - \Phi(d_i))\\
\\
  & = & \sum_{i=1}^j a_i + \sum_{i=1}^j (\Phi(d_{i-1}) - \Phi(d_i)) \\
\\
  & = & \sum_{i=1}^j a_i + \Phi(d_0) - \Phi(d_j)
\end{array}
$$
Суммы вроде $\sum_{i=1}^j (\Phi(d_{i-1}) + \Phi(d_i))$, где
чередующиеся отрицательные и положительные члены взаимно уничтожаются,
называются \term{телескопическими последовательностями}{telescoping
  series}. Если $\Phi$ выбран таким образом, что
$\Phi(d_0)$ равен нулю, а $\Phi(d_j)$ неотрицателен, мы имеем
$\Phi(d_j) \ge \Phi(d_0)$, так что, как и требуется, текущая общая
амортизированная стоимость является верхней границей для текущей общей
реальной стоимости.

\begin{remark}
  Такое описание метода физика несколько упрощает
  картину. Часто при анализе оказывается трудно втиснуть реальное
  положение дел в указанные рамки. Например, что делать с функциями,
  которые порождают или возвращают более одного объекта? Однако даже
  упрощенное описание достаточно для демонстрации основных идей.
\end{remark}

Ясно, что два метода анализа весьма похожи. Можно преобразовать метод
банкира в метод физика, если игнорировать распределение по ячейкам, и
считать, что потенциал равен общему количеству единиц кредита в
объекте, как указано в инварианте кредита. Подобным образом, можно
преобразовать метод физика в метод банкира, если расположить весь
кредит в корне объекта. Возможно, несколько удивляет то, что знание о
расположении ячеек не дает никакой дополнительной мощности в
доказательстве, но методы на самом деле эквивалентны \cite{Tarjan1985,
  Schoenmakers1992}. Чаще всего метод физика оказывается проще, но
иногда бывает удобно принять во внимание распределение по ячейкам.

Заметим, что кредит и потенциал являются лишь средствами анализа; ни
то, ни другое не присутствует в тексте программы (разве что, возможно,
в комментариях).

\section{Очереди}
\label{sc:5.2}

Мы демонстрируем методы банкира и физика через анализ простой
функциональной реализации FIFO-очередей, чья сигнатура приведена на
Рис.~\ref{fig:5.1}.

\begin{figure}

  \centering
\begin{lstlisting}
signature QUEUE =
sig
  type $\alpha$ Queue
  val empty : $\alpha$ Queue
  val isEmpty : $\alpha$ Queue $\to$ bool
  val snoc : $\alpha$ Queue $\times$ $\alpha$ $\to$ $\alpha$ Queue
  val head : $\alpha$ Queue $\to$ $\alpha$            /*$\mbox{ возбуждает исключение } Empty, \mbox{ если очередь пуста }$*/
  val tail : $\alpha$ Queue $\to$ $\alpha$ Queue /*$\mbox{ возбуждает исключение } Empty, \mbox{ если очередь пуста } $*/
end
\end{lstlisting}

  \caption{Сигнатура для очередей. (Этимологическое замечание:
    \lstinline!snoc! представляет собой перевернутое слово
    \lstinline!cons! и означает <<добавить справа>>.)}
  \label{fig:5.1}
\end{figure}

Самая распространенная чисто функциональная реализация очередей
представляет собой пару списков, \lstinline!f! и \lstinline!r!, где
\lstinline!f! содержит головные элементы очереди в правильном порядке,
а \lstinline!r! состоит из хвостовых элементов в обратном порядке.
Например, очередь, содержащая целые числа 1\ldots 6, может быть
представлена списками \lstinline!f=[1,2,3]! и
\lstinline!r=[6,5,4]!. Это представление можно описать следующим
типом:
\begin{lstlisting}
  type $\alpha$ Queue = $\alpha$ list $\times$ $\alpha$ list
\end{lstlisting}
В этом представлении голова очереди~--- первый элемент \lstinline!f!,
так что функции \lstinline!head! и \lstinline!tail!
возвращают и отбрасывают этот элемент, соответственно.
\begin{lstlisting}
  fun head (x :: f, r) = x
  fun tail (x :: f, r) = f
\end{lstlisting}
Подобным образом, хвостом очереди является первый элемент
\lstinline!r!, так что \lstinline!snoc! добавляет к \lstinline!r!
новый элемент.
\begin{lstlisting}
  fun snoc ((f,r), x) = (f, x :: r)
\end{lstlisting}
Элементы добавляются к \lstinline!r! и убираются из \lstinline!f!, так
что они должны как-то переезжать из одного списка в другой. Этот
переезд осуществляется путем обращения \lstinline!r! и установки его
на место \lstinline!f! всякий раз, когда в противном случае
\lstinline!f! оказался бы пустым. Одновременно \lstinline!r!
устанавливается в \lstinline![]!. Наша цель~--- поддерживать
инвариант, что список \lstinline!f! может быть пустым только в том
случае, когда список \lstinline!r! также пуст (т.~е., пуста вся
очередь). Заметим, что если бы \lstinline!f! был пустым при непустом
\lstinline!r!, то первый элемент очереди находился бы в конце
\lstinline!r!, и доступ к нему занимал бы $O(n)$ времени. Поддерживая
инвариант, мы гарантируем, что функция \lstinline!head! всегда может
найти голову очереди за $O(1)$ времени.

Теперь \lstinline!snoc! и \lstinline!tail! должны распознавать
ситуацию, которая может привести к нарушению инварианта, и
соответствующим образом менять свое поведение.
\begin{lstlisting}
  fun snoc (([], _), x) = ([x], [])
    | snoc ((f,r), x) = (f,  x :: r)
  fun tail ([x], r) = (rev r, [])
    | tail (x :: f, r) = (f, r)
\end{lstlisting}
Заметим, что в первой ветке \lstinline!snoc! используется
образец-заглушка. В этом случае поле \lstinline!r! проверять не нужно,
поскольку из инварианта мы знаем, что если список \lstinline!f! равен
\lstinline![]!, то \lstinline!r! также пуст.

Чуть более изящный способ записать эти функции~--- вынести те части
\lstinline!snoc! и \lstinline!tail!, которые поддерживают инвариант, в
отдельную функцию \lstinline!checkf!. Она заменяет \lstinline!f! на
\lstinline!rev r!, если \lstinline!f! пуст, а в противном случае
ничего не делает.
\begin{lstlisting}
  fun checkf ([], r) = (rev r, [])
    | checkf q = q

  fun snoc ((f,r), x) = checkf (f, x :: r)
  fun tail (x :: f, r) = checkf (f, r)
\end{lstlisting}
Полный код реализации показан на Рис.~\ref{fig:5.2}. Функции
\lstinline!snoc! и \lstinline!head! всегда завершаются за время
$O(1)$, но \lstinline!tail! в худшем случае отнимает $O(n)$
времени. Однако, используя либо метод банкира, либо метод физика, мы
можем показать, что как \lstinline!snoc!, так и \lstinline!tail!
занимают амортизированное время $O(1)$.

\begin{figure}
  \centering

  \caption{Распространенная реализация чисто функциональной очереди.}
  \label{fig:5.2}
\end{figure}

В методе банкира мы поддерживаем инвариант, что каждый элемент в
хвостовом списке связан с одной единицей кредита. Каждый вызов
\lstinline!snoc! для непустой очереди занимает один реальный шаг и
выделяет одну единицу кредита для элемента хвостового списка; таким
образом, общая амортизированная стоимость равна двум. Вызов
\lstinline!tail!, не обращающий хвостовой список, занимает один шаг,
не выделяет и не тратит никакого кредита, и, таким образом, имеет
амортизированную стоимость 1. Наконец, вызов \lstinline!tail!,
обращающий хвостовой список, занимает $m+1$ реальный шаг, где $m$~---
длина хвостового списка, и тратит $m$ единиц кредита, содержащиеся в
этом списке, так что амортизированная стоимость получается $m + 1 - m
= 1$.

В методе физика мы определяем функцию потенциала $\Phi$ как длину
хвостового списка. Тогда всякий \lstinline!snoc! к непустой очереди
занимает один реальный шаг и увеличивает потенциал на единицу, так что
амортизированная стоимость равна двум. Вызов \lstinline!tail! без
обращения хвостовой очереди занимает один реальный шаг и не изменяет
потенциал, так что амортизированная стоимость равна одному. Наконец,
вызов \lstinline!tail! с обращением очереди занимает $m+1$ реальный
шаг, но при этом устанавливает хвостовой список равным \lstinline![]!,
уменьшая таким образом потенциал на $m$, так что амортизированная
стоимость равна $m + 1 - m = 1$.

В этом простом примере доказательства почти одинаковы. Но даже при
этом метод физика оказывается чуть проще по следующей причине.
Используя метод банкира, мы должны сначала выбрать инвариант кредита,
а затем для каждой функции решить, когда она должна выделять или
расходовать кредит. Инвариант кредита подсказывает нам, как это
сделать, но решение все же не принимается автоматически. Например,
должен ли \lstinline!snoc! выделить одну единицу кредита и израсходовать
ноль, или выделить две и одну израсходовать? Общий результат
оказывается один и тот же, так что дополнительная свобода оказывается
лишь дополнительным возможным источником путаницы. С другой стороны, в
методе физика от нас требуется принять только одно решение~--- выбрать
функцию потенциала. После этого анализ сводится к простым вычислениям;
никакой свободы выбора не остается.

\begin{hint}
  Эта реализация очередей идеальна в приложениях, где не требуется
  устойчивости и где приемлемы амортизированные показатели
  производительности.
\end{hint}

\begin{exercise}\label{ex:5.1}
  \textbf{Хогерворд \cite{Hoogerwoord1992}.}  Идея этих очередей легко
  может быть расширена на абстракцию \term{двусторонней очереди}{double-ended
    queue}, или \term{дека}{deque}, где чтение и запись разрешены с
  обоих концов очереди (см. Рис.~\ref{fig:5.3}). Инвариант делается
  симметричным относительно \lstinline!f! и \lstinline!r!: если
  очередь содержит более одного элемента, оба списка должны быть
  непустыми. Когда один из списков становится пустым, мы делим другой
  пополам и одну из половин обращаем.

  \begin{enumerate}
  \item Реализуйте эту версию деков.
  \item Докажите, что каждая операция занимает $O(1)$ амортизированного
    времени, используя функцию потенциала $\Phi(f,r) = abs(|f| -
    |r|)$, где $abs$~--- функция модуля.
  \end{enumerate}
\end{exercise}

\begin{figure}
  \centering

  (* вставка, просмотр и уничтожение головного элемента *)\\
  (* возбуждает исключение \lstinline!Empty!, если очередь пуста *)\\
  (* возбуждает исключение \lstinline!Empty!, если очередь пуста *)\\

  (* вставка, просмотр и уничтожение хвостового элемента *)\\
  (* возбуждает исключение \lstinline!Empty!, если очередь пуста *)\\
  (* возбуждает исключение \lstinline!Empty!, если очередь пуста *)\\

  \caption{Сигнатура двусторонней очереди.}
  \label{fig:5.3}
\end{figure}

\section{Биномиальные кучи}
\label{sc:5.3}

В Разделе~\ref{sc:3.2} мы показали, что вставка в биномиальную кучу
проходит в худшем случае за время $O(\log n)$. Здесь мы доказываем,
что на самом деле амортизированное ограничение на время вставки
составляет $O(1)$.

Мы пользуемся методом физика. Определим потенциал биномиальной кучи
как число деревьев в ней.  Заметим, что это число равно количеству
единиц в двоичном представлении $n$, числа элементов в куче.  Вызов
\lstinline!insert! занимает $k+1$ шаг, где $k$~--- число обращений к
\lstinline!link!. Если изначально в куче было $t$ деревьев, то после
вставки окажется $t - k + 1$ деревьев. Таким образом, изменение
потенциала составляет $(t - k + 1) - t = 1 - k$, а амортизированная
стоимость вставки $(k + 1) - (1 - k) = 2$.

\begin{exercise}\label{ex:5.2}
  Повторите доказательство с использованием метода банкира.
\end{exercise}

Для полноты картины нам нужно показать, что амортизированная стоимость
операций \lstinline!merge! и \lstinline!deleteMin! по-прежнему
составляет $O(\log n)$. \lstinline!deleteMin! не доставляет здесь
никаких трудностей, но в случае \lstinline!merge! требуется небольшое
расширение метода физика. До сих пор мы определяли амортизированную
стоимость операции как
$$
a = t + \Phi(d_{\mbox{\textit{вых}}}) - \Phi(d_{\mbox{\textit{вх}}})
$$
где $d_{\mbox{\textit{вх}}}$~--- структура на входе операции, а $d_{\mbox{\textit{вых}}}$~---
структура на выходе. Однако если операция принимает либо возвращает
более одного объекта, это определение требуется обобщить до
$$
a = t + \sum_{d \in \mbox{\textit{Вых}}} \Phi(d) - \sum_{d \in \mbox{\textit{Вх}}} \Phi(d)
$$
где $\mbox{\textit{Вх}}$~--- множество входов, а $\mbox{\textit{Вых}}$~--- множество выходов. В этом
правиле мы рассматриваем только входы и выходы анализируемого типа.

\begin{exercise}\label{ex:5.3}
  Докажите, что амортизированная стоимость операций \lstinline!merge!
  и \lstinline!deleteMin! по-прежнему составляет $O(\log n)$.
\end{exercise}

\section{Расширяющиеся кучи}
\label{sc:5.4}

\term{Расширяющиеся деревья}{splay trees} \cite{SleatorTarjan1985}~--- возможно, самая известная
и успешно применяемая амортизированная структура данных. Расширяющиеся
деревья являются ближайшими родственниками двоичных сбалансированных
деревьев поиска, но они не хранят никакую информацию о балансе
явно. Вместо этого каждая операция перестраивает дерево при помощи
некоторых простых преобразований, которые имеют тенденцию увеличивать
сбалансированность. Несмотря на то, что каждая конкретная операция
может занимать до $O(n)$ времени, амортизированная стоимость ее, как
мы покажем, не превышает $O(\log n)$.

Важное различие между расширяющимися деревьями и сбалансированными
двоичными деревьями поиска вроде красно-чёрных деревьев из
Раздела~\ref{sc:3.3} состоит в том, что расширяющиеся деревья
перестраиваются даже во время запросов (таких, как \lstinline!member!),
а не только во время обновлений (таких, как \lstinline!insert!). Это
свойство мешает использованию расширяющихся деревьев для реализации
абстракций вроде множеств или конечных отображений в чисто
функциональном окружении, поскольку приходилось бы возвращать в
запросе новое дерево наряду с ответом на запрос\footnote{%
В Стандартном ML можно было бы хранить корень расширяющегося дерева в
ссылочной ячейке и обновлять значение по ссылке при каждом запросе, но
такое решение не является чисто функциональным.
}.
Однако в некоторых абстракциях операции-запросы достаточно ограничены,
чтобы эту проблему можно было обойти. Хорошим примером служит
абстракция кучи, поскольку здесь единственным интересным запросом
является \lstinline!findMin!. Как мы увидим, расширяющиеся деревья дают
нам отличную реализацию кучи.

Представление расширяющихся деревьев идентично представлению
несбалансированных двоичных деревьев поиска.
\begin{lstlisting}
  datatype Tree = E | T of Tree $\times$ Elem.T $\times$ Tree
\end{lstlisting}
Однако в отличие от несбалансированных двоичных деревьев поиска из
Раздела~\ref{sc:2.2}, мы позволяем дереву содержать повторяющиеся
элементы. Эта разница не является фундаментальным различием расширяющихся
деревьев и несбалансированных двоичных деревьев поиска; она просто
отражает отличие абстракции множества от абстракции кучи.

Рассмотрим следующую стратегию реализации для \lstinline!insert!:
разобьем существующее дерево на два поддерева, чтобы одно содержало все
элементы, меньше или равные новому, а второе все элементы, большие
нового. Затем породим новый узел из нового элемента и двух этих
поддеревьев. В отличие от вставки в обыкновенное двоичное дерево
поиска, эта процедура добавляет элемент как корень дерева, а не как
новый лист. Код для \lstinline!insert! выглядит просто как
\begin{lstlisting}
  fun insert (x, t) = T (smaller (x, t), x, bigger (x, t))
\end{lstlisting}
где \lstinline!smaller! выделяет дерево из элементов, меньше или равных
\lstinline!x!, а \lstinline!bigger! дерево из элементов, больших
\lstinline!x!. По аналогии с фазой разделения быстрой сортировки,
назовем новый элемент \term{границей}{pivot}.

Можно наивно реализовать \lstinline!bigger! как
\begin{lstlisting}
  fun bigger (pivot, E) = E
    | bigger (pivot, T (a, x, b)) =
        if x $\le$ pivot then bigger (pivot, b)
        else T (bigger (pivot, a), x, b)
\end{lstlisting}
однако при таком решении не делается никакой попытки перестроить
дерево, добиваясь лучшего баланса.  Вместо этого мы применяем простую
эвристику для перестройки: каждый раз, пройдя по двум левым ветвям
подряд, мы проворачиваем два пройденных узла.
\begin{lstlisting}
  fun bigger (pivot, E) = E
    | bigger (pivot, T a, x, b)) =
        if x $\le$ pivot then bigger (pivot, b)
        else case a of
               E $\Rightarrow$ T (E, x, b)
             | T (a$_1$, y, a$_2$) $\Rightarrow$
                  if y $\le$ pivot then T (bigger (pivot, a$_2$), x, b)
                  else T (bigger (pivot. a$_1$), y, T (a$_2$, x, b))
\end{lstlisting}
На Рис.~\ref{fig:5.4} показано, как \lstinline!bigger! действует на
сильно несбалансированное дерево. Несмотря на то, что результат
по-прежнему не является сбалансированным в обычном смысле, новое
дерево намного сбалансированнее исходного; глубина каждого узла
уменьшилась примерно наполовину, от $d$ до $\lfloor d/2 \rfloor$ или
$\lfloor d/2 \rfloor + 1$. Разумеется, мы не всегда можем уполовинить
глубину каждого узла в дереве, но мы можем уполовинить глубину каждого
узла, лежащего на пути поиска. В сущности, в этом и состоит принцип
расширяющихся деревьев: нужно перестраивать путь поиска так, чтобы
глубина каждого лежащего на пути узла уменьшалась примерно вполовину.

\begin{figure}
  \centering
  \input{figures/fig.5.4.tex}
  \caption{Вызов функции \lstinline!bigger! с граничным элементом 0.}
  \label{fig:5.4}
\end{figure}

\begin{exercise}\label{ex:5.4}
  Реализуйте операцию \lstinline!smaller!. Не забудьте, что
  \lstinline!smaller! должна сохранять элементы, равные границе (однако
   устраивать отдельную проверку на равенство не следует!).
\end{exercise}

Заметим, что \lstinline!smaller! и \lstinline!bigger! вегда проходят
по одному и тому же пути поиска. Вместо того, чтобы повторять это
прохождение дважды, можно соединить \lstinline!smaller! и
\lstinline!bigger! в единую функцию с названием \lstinline!partition!,
которая вернет оба результата в виде пары.  Написание этой функции не
представляет труда, но несколько утомительно.
\begin{lstlisting}
  fun partition (pivot, E) = (E, E)
    | partition (pivot, t as T (a, x, b)) =
       if x $\le$ pivot then
         case b of
           E $\Rightarrow$ (t, E)
         | T (b$_1$, y, b$_2$) $\Rightarrow$
              if y $\le$ pivot then
                  let val (small, big) = partition (pivot, b$_2$)
                  in (T (T (a, x, b$_1$), y, small), big) end
              else
                  let val (small, big) = partition (pivot, b$_1$)
                  in (T (a, x, small), T (big, y, b$_2$)) end
       else
         case a of
           E $\Rightarrow$ (E, t)
         | T (a$_1$, y, a$_2$) $\Rightarrow$
              if y $\le$ pivot then
                  let val (small, big) = partition (pivot, a$_2$)
                  in (T (a$_1$, y, small), T (big, x, b)) end
              else
                  let val (small, big) = partition (pivot, a$_1$)
                  in (small, T (big, y, T (a$_2$, x, b))) end
\end{lstlisting}

\begin{remark}
  Эта функция не является точным эквивалентом \lstinline!smaller! и
  \lstinline!bigger! из-за расхождения фаз: \lstinline!partition!
  всегда обрабатывает узлы парами, а \lstinline!smaller! и
  \lstinline!bigger! иногда проходят по одному узлу.  Поэтому иногда
  \lstinline!smaller! и \lstinline!bigger! оборачивают не те же самые
  узлы, что \lstinline!partition!. Однако ни к каким важным
  последствиям это расхождение не приводит.
\end{remark}

Рассмотрим теперь \lstinline!findMin! и
\lstinline!deleteMin!. Минимальный элемент расширяющегося дерева
хранится в самой левой его вершине типа \lstinline!T!. Найти эту
вершину несложно.
\begin{lstlisting}
  fun findMin (T (E, x, b)) = x
    | findMin (T (a, x, b)) = findMin a
\end{lstlisting}
Функция \lstinline!deleteMin! должна уничтожить самый левый узел и
одновременно перестроить дерево таким же образом, как это делает
\lstinline!bigger!. Поскольку мы всегда рассматриваем только левую
ветвь, сравнения не нужны.
\begin{lstlisting}
  fun deleteMin (T (E, x, b)) = b
    | deleteMin (T (T (E, x, b), y, c)) = T (b, y, c)
    | deleteMin (T (T (a, x, b), y, c)) = T (deleteMin a, x, T (b, y, c))
\end{lstlisting}
На Рис.~\ref{fig:5.5} реализация расширяющихся
деревьев приведена целиком. Для полноты мы включили в нее функцию слияния
\lstinline!merge!, хотя она довольно неэффективна и для многих входов
занимает $O(n)$ времени.

\begin{figure}
  \centering

  \caption{Реализация кучи через расширяющиеся деревья.}
  \label{fig:5.5}
\end{figure}

Теперь мы хотим показать, что \lstinline!insert! выполняется за время
$O(\log n)$. Пусть $\#t$ обозначает размер дерева $t$ плюс
один. Заметим, что если $t = \lstinline!T($a$, $x$, $b$)!$, то $\#t =
\#a + \#b$. Пусть потенциал вершины $\phi(t)$ равен $\log(\# t)$, а
потенциал всего дерева равен сумме потенциалов его вершин. Нам
требуется следующее элементарное утверждение, касающееся логарифмов:
\begin{lemma}\label{lm:5.1}
  Для всех положительных $x, y, z$, таких, что $y + z \le x$,
  $$
  1 + \log y + \log z < 2 \log x
  $$

  \noindent
  \textit{Доказательство.} Без потери общности предположим, что $y \le  z$.
  Тогда $y \le x/2$ и $z \le x$, так что $1 + \log y \le \log x$ и
  $\log z < \log x$
\end{lemma}

Пусть $\mathcal{T}(t)$ обозначает реальную стоимость вызова
\lstinline!partition! для дерева $t$, что определяется как число
рекурсивных вызовов \lstinline!partition!. Пусть $\mathcal{A}(t)$~---
амортизированная стоимость такого вызова, определяемая как
$$
\mathcal{A}(t) = \mathcal{T}(t) + \Phi(a) + \Phi(b) - \Phi(t)
$$
где $a$ и $b$~--- возвращаемые функцией \lstinline!partition!
поддеревья.

\begin{theorem}\label{th:5.2}
  $\mathcal{A}(t) \le 1 + 2\phi(t) = 1 + 2\log(\#t)$

  \noindent\textit{Доказательство.} Требуется рассмотреть два
  нетривиальных случая, называемые зиг-зиг и зиг-заг, в зависимости
  от того, проходит ли вызов \lstinline!partition! по двум левым
  ветвям (или, симметрично, по двум правым), либо по левой ветке, а
  затем правой (или, симметрично, по правой, а затем по левой).

  Для случая зиг-зиг предположим, что исходное и результирующее дерево
  имеют формы

\begin{center}
  \input{figures/formula.theorem.5.2.tex}
\end{center}
где $a$ и $b$ являются результатами вызова \lstinline!partition (pivot, u)!. Тогда
$$
\begin{array}{ll}
  & \mathcal{A}(s) \\
= & \qquad\{\mbox{ по определению $\mathcal{A}$ }\} \\
  & \mathcal{T}(s) + \Phi(a) + \Phi(s') - \Phi(s) \\
= & \qquad\{\mbox{ $\mathcal{T}(s) = 1 + \mathcal{T}(u)$ }\} \\
  & 1 + \mathcal{T}(u) + \Phi(a) + \Phi(s') - \Phi(s) \\
= & \qquad\{\mbox{ $\mathcal{T}(u) = \mathcal{A}(u) - \Phi(a) - \Phi(b) + \Phi(u)$ }\} \\
  & 1 + \mathcal{A}(u) - \Phi(a) - \Phi(b) + \Phi(u) + \Phi(a) + \Phi(s') - \Phi(s) \\
= & \qquad\{\mbox{ раскрываем $\Phi(s)$ и $\Phi(s')$, упрощаем }\} \\
  & 1 + \mathcal{A}(u) + \phi(s') + \phi(t') - \phi(s) - \phi(t) \\
\le & \qquad\{\mbox{ по предположению индукции, $\mathcal{A}(u) \le 1 + 2\phi(u)$ } \} \\
  & 2 + 2\phi(u) + \phi(s') + \phi(t') - \phi(s) - \phi(t) \\
< & \qquad \{\mbox{$\phi(u) < \phi(t)$, а $\phi(s') \le \phi(s)$}\} \\
  & 2 + \phi(u) + \phi(t') \\
< & \qquad \{\mbox{ $\#u + \#t' < \#s$, а также Лемма~\ref{lm:5.1} }\} \\
  & 1 + 2\phi(s) \\
\end{array}
$$
Доказательство случая зиг-заг мы оставляем как упражнение для читателя.

\begin{exercise}\label{ex:5.5}
  Докажите случай зиг-заг.
\end{exercise}

Дополнительная стоимость операции \lstinline!insert! по сравнению с
\lstinline!partition! составляет один реальный шаг плюс разница
потенциалов между двумя поддеревьями-результатами
\lstinline!partition! и деревом-окончательным результатом
\lstinline!insert!. Это изменение потенциала равно просто $\phi$ от
нового корня. Поскольку амортизированная стоимость
\lstinline!partition! ограничена $1 + 2\log(\#t)$, амортизированная
стоимость \lstinline!insert! ограничена
$2 + 2\log(\#t) + \log(\#t + 1) \approx 2 + 3\log(\#t)$.

\end{theorem}

\begin{exercise}\label{ex:5.6}
  Докажите, что стоимость \lstinline!deleteMin! также составляет
  $O(\log n)$.
\end{exercise}

Какова ситуация с \lstinline!findMin!? Если дерево сильно
несбалансированно, \lstinline!findMin! может занять до $O(n)$
времени. Причем поскольку \lstinline!findMin! не проводит никакой
перестройки и, следовательно, никак не изменяет потенциал,
амортизировать эту стоимость негде! Однако раз время
\lstinline!findMin! пропорционально времени \lstinline!deleteMin!,
мы можем увеличить стоимость, взимаемую за \lstinline!deleteMin!,
вдвое, и один раз на каждый ее вызов бесплатно звать
\lstinline!findMin!. Этого достаточно для тех приложений, которые
всегда зовут \lstinline!findMin! и \lstinline!deleteMin!
вместе. Однако в некоторых приложениях \lstinline!findMin! может
вызываться по несколько раз на каждый вызов \lstinline!deleteMin!. Для
этих приложений мы не будем напрямую вызывать функтор
\lstinline!SplayHeap!, а будем его использовать в комбинации с
функтором \lstinline!ExplicitMin! из
Упражнения~\ref{ex:3.7}. Напомним, что задачей функтора
\lstinline!ExplicitMin! было обеспечить выполнение \lstinline!findMin!
за время $O(1)$. Функции \lstinline!insert! и \lstinline!deleteMin!
по-прежнему будут выполняться за время $O(\log n)$.

\begin{hint}
  Расширяющиеся деревья, дополняемые при необходимости функтором
  \lstinline!ExplicitMin!,~--- самая быстрая из известных реализаций
  кучи для большинства приложений, не требующих устойчивости данных и
  не вызывающих функцию \lstinline!merge!.
\end{hint}

Особенно приятным свойством расширяющихся деревьев является то, что
они естественным образом подстраиваются под любой порядок,
присутствующий во входных данных. Например, при использовании
расширяющихся деревьев для сортировки уже сортированного заранее
списка тратится всего $O(n)$ времени, а не $O(n \log n)$
\cite{MoffatEddyPetersson1996}. Тем же свойством обладают
левоориентированные кучи, но только для уменьшающихся
последовательностей. Расширяющиеся кучи отлично себя ведут как на
растущих, так и на уменьшающихся последовательностях, а также на
последовательностях, отсортированных лишь частично.

\begin{exercise}\label{ex:5.7}
  Напишите функцию сортировки, которая складывает элементы в
  расширяющееся дерево, а затем обходит его по порядку, выводя
  элементы в список. Покажите, что на уже отсортированном списке она
  работает за время всего $O(n)$.
\end{exercise}

\section{Парные кучи}
\label{sc:5.5}

\term{Парные кучи}{pairing heaps} \cite{Fredman-etal1986}~--- одна из тех структур, которые
сводят специалистов с ума. С одной стороны, их легко реализовать и они
весьма хорошо показали себя на практике. С другой стороны, провести их
полный анализ не удается уже более 10 лет!

Парные кучи представляют собой упорядоченные по принципу кучи деревья
с переменной степенью ветвления; их можно определить следующим типом
данных:
\begin{lstlisting}
  datatype Heap = E | T of Elem.T $\times$ Heap list
\end{lstlisting}
Мы считаем правильными только такие деревья, где \lstinline!E! никогда
не встречается в качестве ребенка вершины \lstinline!T!.

Поскольку деревья упорядочены по принципу кучи, функция
\lstinline!findMin! тривиальна:
\begin{lstlisting}
  fun findMin (T (x, hs)) = x
\end{lstlisting}
Функции \lstinline!merge! и \lstinline!insert! ненамного
сложнее. \lstinline!merge! добавляет то дерево, чей корень больше, в
качестве первого ребенка того дерева, чей корень
меньше. \lstinline!insert! сначала создает новое дерево с одним
элементом, а затем зовет \lstinline!merge!.
\begin{lstlisting}
  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h$_1$ as T (x, hs$_1$), h$_2$ as T (y, hs$_2$)) =
       if Elem.leq (x, y) then T (x, h$_2$ :: hs$_1$) else T (y, h$_1$ :: hs$_2$)
  fun insert (x, h) = merge (T(x, []), h)
\end{lstlisting}
Парные деревья называются именно так благодаря операции
\lstinline!deleteMin!. Эта операция отбрасывает корень, а затем
сливает деревья в два прохода. Первый проход сливает деревья парами
слева направо (т.~е., первое дерево сливается со вторым, третье с
четвертым и т.~д.). При втором проходе получившиеся деревья сливаются
справа налево. Эти два прохода можно кратко выразить так:
\begin{lstlisting}
  fun mergePairs [] = E
    | mergePairs [h] = h
    | mergePairs (h$_1$ :: h$_2$ :: hs) = merge (merge (h$_1$, h$_2$), mergePairs hs)
\end{lstlisting}
После этого \lstinline!deleteMin! выглядит совсем просто:
\begin{lstlisting}
  fun deleteMin (T (x, hs)) = mergePairs hs
\end{lstlisting}
Полная реализация приведена на Рис.~\ref{fig:5.6}

\begin{figure}
  \centering

  \caption{Парные кучи.}
  \label{fig:5.6}
\end{figure}

Легко видеть, что \lstinline!findMin!, \lstinline!insert! и
\lstinline!merge! занимают каждая по $O(1)$ времени. Однако в худшем
случае \lstinline!deleteMin! может отнять до $O(n)$. По аналогии с
расширяющимися деревьями (см. Упражнение~\ref{ex:5.8}) мы можем
показать, что \lstinline!insert!, \lstinline!merge! и
\lstinline!deleteMin! каждая отнимает по $O(\log n)$ амортизированного
времени. Существует предположение, что \lstinline!insert! и
\lstinline!merge! на самом деле работают за амортизированное время
$O(1)$ \cite{Fredman-etal1986}, но его до сих пор никому не удалось ни
доказать, ни опровергнуть.

\begin{hint}
  В приложениях, где не требуется функция \lstinline!merge!, парные
  кучи работают почти так же быстро, как расширяющиеся кучи, а если
  \lstinline!merge! требуется, то они значительно быстрее.  Подобно
  расширяющимся кучам, их следует применять только в тех приложениях,
  где устойчивость не требуется.
\end{hint}

\begin{exercise}\label{ex:5.8}
  Часто проще оказывается работать с двоичными деревьями, чем с деревьями с
  произвольным ветвлением. К счастью, любое дерево с произвольным
  ветвлением легко представить в виде двоичного. Достаточно
  преобразовать каждый узел со списком детей в двоичный узел, где левый ребенок
  представляет самого левого ребенка исходного узла, а правый
  потомок представляет его сестринский узел непосредственно
  справа. Если отсутствуют либо левый узел, либо правый сосед, то
  соответствующий узел двоичного дерева оказывается пустым. (Заметим,
  что таким образом в двоичном представлении правый потомок корневого
  узла всегда оказывается пуст.) Применив такое преобразование к парной
  куче, мы получаем полуупорядоченные двоичные деревья, где элемент в
  каждом узле не больше любого элемента в своем левом дочернем
  поддереве.
  \begin{enumerate}
  \item Напишите функцию \lstinline!toBinary!, преобразующую парные
    кучи из исходного представления в тип
    \begin{lstlisting}
      datatype BinTree = E' | T' of Elem.T $\times$ BinTree $\times$ BinTree
    \end{lstlisting}
  \item Заново реализуйте парные кучи, используя это новое представление.
  \item Модифицируйте анализ расширяющихся деревьев и докажите, что
    \lstinline!deleteMin! и \lstinline!merge! работают за
    амортизированное время $O(\log n)$ в этом новом представлении (а
    следовательно, и в старом тоже). Следует использовать ту же самую
    функцию потенциала, как и в расширяющихся деревьях.
  \end{enumerate}
\end{exercise}

\section{Плохая новость}
\label{sc:5.6}

Как мы могли убедиться, амортизированные структуры могут быть
чрезвычайно эффективны на практике. К сожалению, все рассуждения в
этой главе неявно предполагают, что анализируемые структуры данных
используются эфемерным образом (то есть, только одной нитью
последовательных операций). Что произойдет, если мы попытаемся с теми же
самыми структурами обращаться как с устойчивыми?

Рассмотрим очереди из Раздела~\ref{sc:5.2}. Пусть $q$ будет очередь,
получаемая вставкой $n$ элементов в изначально пустую очередь, так что
головной список $q$ содержит один элемент, а хвостовой $n - 1$
элементов. Теперь предположим, что мы считаем очередь устойчивой и $n$
раз удаляем первый элемент. Каждый из этих вызовов отнимет $n$
реальных шагов.  Общая реальная стоимость этой последовательности
операций, включая изначальное построение $q$, равна $n^2 + n$. Если бы
операции на самом деле отнимали только по $O(1)$ амортизированного
времени, общая реальная стоимость была бы всего $O(n)$. Таким образом,
ясно, что использование наших очередей как устойчивой структуры
нарушает установленные в Разделе~\ref{sc:5.2} амортизированные
ограничения стоимости $O(1)$. Где же ошибка в доказательствах?

В обоих случаях одно из основных предположений доказательства
оказывается нарушенным при рассмотрении структуры как устойчивой. В
методе банкира требуется, чтобы каждая единица кредита тратилась не
более одного раза, а метод физика требует, чтобы результат одной
операции служил аргументом следующей (или, в более общей формулировке,
чтобы всякий результат операции использовался как аргумент другой не
более одного раза).  Рассмотрим второе обращение к \lstinline!tail q!
в вышеописанном примере. Первое обращение тратит весь кредит,
накопленный в хвостовом списке $q$, и оказывается нечем оплатить
второй и последующие вызовы, так что метод банкира терпит
неудачу. Кроме того, второе обращение к \lstinline!tail q! повторно
использует $q$, а не результат первого вызова, так что метод физика
тоже не работает.

Обе неудачных попытки доказательства отражают слабость всякой
системы подсчета, основанной на накоплениях~--- то, что эти накопления
можно потратить лишь один раз. Традиционные методы амортизации
работают путем накопления единиц работы (либо кредита, либо
потенциала) для дальнейшего использования. Это отлично работает при
эфемерном использовании, когда у каждой операции лишь одно логическое
будущее. Но у операции над устойчивой структурой может быть сколько угодно
логических будущих, и в каждом из них структура может пытаться потратить
одни и те же накопления.

В следующей главе мы разъясним, что имеется в виду под <<логическим
будущим>> операции, и как можно совместить амортизацию и устойчивость
через ленивое вычисление.

\begin{exercise}\label{ex:5.9}
  Приведите примеры последовательности операций, где биномиальные
  кучи, расширяющиеся кучи и парные кучи отнимают намного больше
  времени, чем указывают амортизированные границы их стоимости.
\end{exercise}

\section{Примечания}

Методы амортизации, обсуждаемые в этой главе, были разработаны
Слейтором и Тарьяном \cite{SleatorTarjan1985, SleatorTarjan1986b}. Они
стали популярны благодаря Тарьяну \cite{Tarjan1985}. Схунмакерс
\cite{Schoenmakers1992} показывает, как систематическим образом
получать амортизированные оценки стоимости при функциональном
программировании без использования устойчивости.

Кучи из Раздела~\ref{sc:5.2} были предложены Грисом
\cite[с.~250-251]{Gries1981}, а также Худом и Мелвиллом
\cite{HoodMelville1981}. Бёртон \cite{Burton1982} предложил похожую
реализацию, однако без ограничения, чтобы у непустой кучи головной список всегда был
непуст. У Бёртона \lstinline!head! и \lstinline!tail! объединены в
одну функцию, и, таким образом, нет требования, чтобы \lstinline!head!
по отдельности была эффективна.

В нескольких экспериментальных исследованиях было показано, что
расширяющиеся кучи \cite{Jones1986} и парные кучи
\cite{MoretShapiro1991,Liao1992}~--- одни из самых быстрых
реализаций для этой абстракции. Стаско и Виттер
\cite{StaskoVitter1987} подтвердили для варианта парных куч
предполагаемое амортизированное ограничение $O(1)$ на вставку.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "pfds"
%%% End: