\documentclass[12pt]{article}

\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsthm, amsmath, amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
\usepackage{enumerate}
\usepackage{color}
\usepackage{picture}
\usepackage{hyperref}

\voffset=-20mm
\textheight=220mm

\hoffset=-10mm
\textwidth=155mm

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}

\newenvironment{MyList}{
  \begin{enumerate}[1.]
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{5pt}
}{
  \end{enumerate}
}

\newlength{\myskip}
\setlength{\myskip}{0.5em}

\begin{document}

\begin{center}
  {\Large \bf Лекция по алгоритмам \t{\#4}} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: Кучи} \\
  \vspace{0.5em}
  {\Large 07 октября 2014} \\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}

\vspace{1em}
\tableofcontents
\pagebreak

\section{Inplace Merge}
    Input: два отсортированных массива $a$ и $b$, идущих подряд в памяти (сначала $a$).\\
    Output: отсортированный массив из элементов массивов $a$ и $b$, лежащий на их месте.\\
    $n = |a| + |b|$\\
   \subsection{Merge0. $T = \O\left(n \cdot \log(n)\right)$ $M = \O\left(\log(n)\right)$}
        Пусть $x$ -- медиана большего массива.\\
        Разделим каждый из массивов $a$ и $b$ на 3 части:\\
        1. $a_1, b_1$ -- части, в которых все элементы меньше $x$.\\
        2. $a_2, b_2$ -- равны $x$.\\
        3. $a_3, b_3$ -- больше $x$.\\
        Далее, вызовем \texttt{merge()} от пар $(a_1, b_1)$ и $(a_3, b_3)$.\\
        Новый массив получится таким:
        \texttt{merge($a_1$, $b_1$)} $a_2$ $b_2$ \texttt{merge($a_3$, $b_3$)}\\
        При этом важно, чтобы $a_2$ было раньше $b_2$, для стабильности сортировки. Кстати, заметим, что такая сортировка лучше, чем \texttt{qsort}, так как
        она является стабильной и детерминированной, в отличии от быстрой.\\
        Заметим, что дополнительной памяти требуется $\O(\log(n))$ из-за стека рекурсии и работает эта штука за $\O(n\cdot\log(n))$, т.к. на каждом
        уровне рекурсии надо упорядочить порядка $n$ элементов.
  
    \subsection{Merge1. $T = \Theta\left(n\right)$ $M = \Theta\left(|a| + |b|\right)$}
        Создаем массив $c$ размером $|a| + |b|$. Идем двумя указателями $i$ и $j$ по массивам $a$ и $b$ соответственно и  кладем меньший элемент из $a[i]$ и $b[j]$ в массив $c$, 
        увеличивая соответствующий указатель.
    \subsection{Merge2. $T = \O\left(n\right)$ $M = \O\left(|a|\right)$}
        Создаем массив $c$ длины $|a|$ и копируем в него содержимое массива $a$. Так же, как в Merge0, установим два указателя -- на начало $c$ и
        $b$. Ещё один установим в начало массива $a$, но этот указатель, в отличии от двух предыдущих, будет не для считывания, а для записи.
        На очередной итерации сравниваем элемент массива $c$, в котором находится указатель, с аналогичным элементом массива $b$. Меньший из них
        записываем в массив $a$, соответствующий указатель считывания увеличиваем, увеличиваем указатель записи.\\ 
        Заметим, что мы никогда не обгоним указателем записи в $a$ указатель считывания в $b$, а значит не испортим значений массива $b$.
    \subsection{Merge3. $T = \O\left(n\right)$ $M = \O\left(min(|a|, |b|)\right)$}
        Если массив $a$ короче, чем $b$, то делаем все так же. Иначе, нам придется поменять их местами. Это можно сделать так:\\
        \texttt{
            1. reverse(a)\\
            2. reverse(b)\\
            3. reverse(a+b)\\
        }
        Несложно заметить, что после таких действий массивы $a$ и $b$ действительно поменяются местами. Дальше решаем задачу так же, как в прошлом
        пункте.
    \subsection{Merge5. $T = \O\left(n\right)$ $M = \O\left(1\right)$}
        В общем, такой есть, но он очень сложный. В 1963м году была придумана нестабильная версия. В 96м стабильная.
    \subsection{Экзотика}
        1. $M = \O(1) \quad T = \O(\frac{n \cdot \log n}{\log \log n})$\\
        Прочитать можно \href{http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf}{тут}.\\
        2. $M = \O(1) \quad T = \Theta(m \cdot \log(\frac{n}{m}))$, где n - длина массива $a$, а m - массива $b$.\\
        Прочитать можно \href{http://comjnl.oxfordjournals.org/content/38/8/681.full.pdf+html}{тут}.\\
        Эти и некоторые другие ссылки можно найти \href{http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm}{тут}.\\

\section{MinMax heap}
    Памяти $\O(n)$.\\
    \texttt{GetMin, GetMax} за $\O(1)$.\\
    \texttt{Add, DelMin, DelMax} за $\O(\log n)$.\\
    Модификация двоичной кучи, где каждая вершина удовлетворяет следующему свойству: если она находится на четном уровне, 
    то она меньше всех своих потомков, если на
    нечетном, то больше. Тогда понятно, что её минимум находится в корне, а максимум -- один из детей корня. \texttt{Add, DelMin, GetMin} такие же, как и в двоичной куче.        
    Опишем реализацию \texttt{SiftUp}, \texttt{SiftDown}, \texttt{DelMax}.\\ \\

    \subsection{SiftUp}
    Пусть надо просеить вверх вершину со значением $Х$ и она находится на четном слое (четность слоя можно узнать, просто поднявшись 
    до корня или предподсчитав заранее).
    Тогда, если $X$ уже не является корнем, над ней есть элемент $Max$. Далее, возможны два случая:\\
    1. $X > Max$. Но тогда заметим, что цепь минимумов до корня точно не изменилась, т.к. все они должны быть меньше $Max$, а значит и меньше $X$.
    Меняем местами $X$ и $Max$, а дальше, сравнивая $X$ и следующий максимум (вершину, на 2 уровня выше), просеиваем вверх. После
    очередного свопа свойство этой кучи для поддерева нового положения $X$ не испортятся -- очередной свопнутый максимум ($Max_i$) 
    продолжит быть максимумом на поддереве (т.к. он не перестал быть больше своих потомков), а минимум, лежащий между новыми положениями $X$ и $Max_i$
    не перестанет быть минимумом в своем поддереве, т.к. $Max_i$ больше его.\\
    2. $X \le Max$. Тогда не испортилась цепочка максимумов. Делаем все то же самое, но сравнивая и свопая с ближайшим минимумом.\\
    Если $X$ был на четном уровне, то действия аналогичны, но поменяются знаки сравнений и слова "минимум"  и "максимум".\\

    \subsection{SiftDown}
    Сравниваем данную вершину с внуками (если их нет, то с сыновьями). Если текущая вершина на четном уровне и больше какого-то из внуков, то меняем
    ее местами с минимальным из внуков. Теперь, сравниваем её значение со значением её нового отца. Если она больше, то меняем местами с отцом и
    запускаем \t{SiftDown} от этого места.\\

    \subsection{DelMax}
        Выберем максимум из детей корня. Он - ответ. Поставим на его место последний элемент кучи и просеим его вниз (этот элемент не может быть меньше корня, т.к. он был в
        его поддереве).

\section{HeapBuild: lower bounds}
    Рассмотрим нижние оценки на количество сравнений для построения двоичной кучи из неупорядоченного массива.\\
    \subsection{$T(HeapBuild) \ge n - 1$}
        Корнем двоичной кучи должен быть минимальный элемент, поэтому ее нельзя построить за меньшее число сравнений, чем необходимое для поиска минимума в массиве.\\
        Докажем, что нельзя найти минимум в произвольном массиве меньше, чем за $n - 1$ сравнение.\\
        Рассмотрим граф сравнений (числа - вершины, сравнение двух чисел - ребро между соответствующими им вершинами).\\
        Предположим, что мы нашли минимум меньше, чем за $n-1$ сравнение.\\
        Тогда граф сравнений не связный, т.е. есть хотя бы 2 набора чисел, между элементами которых не было ни одного сравнения. 
        Но, тогда алгоритм сработал бы неверно на одном из следующих массивов:\\
        1. В первой компоненте связности числа от $1$ до $A$, во второй - от $A+1$ до $A+B$, в остальных - что угодно.\\
        2. В первой компоненте связности числа от $B+1$ до $B+A$, во второй - от $1$ до $B$, в остальных - что угодно.\\
        Значит, такого алгоритма не существует и минимальное число сравнений - хотя бы $n-1$.

    \subsection{$T(HeapBuild) \ge 1.3644n$}
        Для доказательства этой оценки применим такое же рассужднеие, как и в доказательстве минимального числа сравнений для сортировки массива.\\
        Пусть число различных двоичных куч из $n$ различных элементов равно $H(n)$.\\
        Тогда, если алгоритм строит корректную кучу, должно выполняться неравенство 
        $2^k \ge \frac{n!}{H(n)}$, где $k$ - число сравнений, сделанных алгоритмом,\\
        иначе, из какой-нибудь из $n!$ перестановок была бы построена некорректная куча.\\
        Значит $k \ge \log_2{\frac{n!}{H(n)}}$.\\
        Но $H(n) = \frac{n!}{\prod{size_i}}$, где $\prod{size_i}$ - произведение размеров всех поддеревьев кучи,\\
        т.к. куч из $n$ элементов с минимумом в корне $\frac{n!}{n}$, а в корне каждого поддерева кучи должен быть минимум.\\
        Значит $k \ge \log_2{\frac{n!}{H(n)}} = \log_2{\prod{size_i}} \ge 1.3644n$. Последнюю часть неравенства доказывать не будем.

\section{Pairing heap}

\subsection{Оценки времени}
    \t{ Add $\O(1)$\\
        Merge $\O(1)$\\
        GetMin $\O(1)$\\
        DelMin $\O(\log n)$\\
        DecreaseKey $o(\log n) \quad (\Omega(\log \log n))$\\
       }
       Все оценки амортизированные.

\subsection{Описание}
    Вся куча -- это список из нескольких куч (список корней). Каждая из этих куч будет выглядеть следующим образом: 
    каждый уровень -- это список вершин (зацикленный), каждая
    из которых хранит значение, ссылается на следующий в этом слое (для данной кучи) элемент и на своего левого ребенка (при этом для
    нее выполнены все свойства кучи). Назовем эти сслыки \t{r} и \t{l} соответственно.

\subsection{Add}
    Добавляет в список новую кучу, содержащуюю единственный элемент -- данное значение.

\subsection{Merge}
    Просто прибавляем один список к другому.

\subsection{Merge(a, b)}
    (Это \t{merge} двух кучек (тех, что лежат в списке) одной кучи)
    Если значение в \t{a} меньше, чем значение в \t{b}, то
    \t{b} теперь будет находится во втором слое кучи с корнем в \t{a}, так что теперь добавляем ее в список детей \t{a} следующем образом:\\
    \t{b} будет иметь ссылку \t{b.r} на текущего самого левого ребенка \t{a} и сам станет самым левым. Т.е. нужно обновить две ссылки:\\
    \t{b.r} = \t{a.l}\\
    \t{a.l} = \t{b}\\
    Если значение в \t{a} меньше, чем значение в \t{b}, то действия аналогичны, но уже \t{a} станет ребенком \t{b}\\

\subsection{Pairing}
    Это собственно операция объединения всего этого списка корней, из которых состоит наша в целом, в одну большую кучу. Это делать мы будем так:
    объединяем две первые, а потом объединим получившуюся кучу с результатом работы \t{Pairing} от оставшегося списка кучек.\\
        \t{\begin{MyList}
          \item \hspace{0em} Pairing(l)
          \item \hspace{2em}   if (|l| == 1)
          \item \hspace{4em}     return l[0]
          \item \hspace{2em}   if (|l| == 2)
          \item \hspace{4em}     return Merge(l[0], l[1])
          \item \hspace{2em}   return Merge(Merge(l[0], l[1]), Pairing(l[2:]))
        \end{MyList}}

\subsection{GetMin}
    Просто всегда помним минимум в списке.

\subsection{DelMin}
    Зная минимум во всем списке, удаляем его, делаем \t{Pairing} от списка его детей, добавляем получившуюся кучку к списку кучек (списку корней).\\
    \t{
    DelMin\\
    1. Del $\O(1)$\\
    2. Pairing $\O(k)$ (где $k$ -- количество детей у удаленной вершины)\\
    }

\subsection{DecreaseKey(x)}
    Удаляем $x$ из списка вершин уровня, в котором он содержался, перенаправив ссылку с родителя (если таковая указывала в $x$) на \t{x.r}.
    $x$ становится новым корнем в списке корней.

\end{document}
