\documentclass[12pt]{article}


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

\usepackage[dvips]{graphicx}
\graphicspath{{/}}


\voffset=-20mm
\textheight=220mm

\hoffset=-20mm
\textwidth=175mm

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}
\newcommand{\q}[1]{\langle #1 \rangle}

\newcommand\Label[1]{\item {\bf #1}}
\def\Begin{$\bullet$\hspace{0.5em}}

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

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

\newcommand\URL[1]{{\footnotesize{\url{#1}}}}

\begin{document}

\begin{center}
  {\Large \bf Лекция по алгоритмам \t{\#5}} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: Кучи} \\
  \vspace{0.5em}
  \begin{normalsize}
  (k-heap, leftist, skew, add in O(1), merge in O(1), build in O(n))\\
  \end{normalsize}
  {\Large 2 сентября} \\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

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

\vspace{1em}
\tableofcontents
\pagebreak

\section{Heap}
	Куча -- структура данных реализующая интерфейс очереди с приоритетами (Priority Queue).\\
\textbf	Basic interface:
	\begin{itemize}
		\item Add (Insert)
		\item GetMin
		\item DelMin
	\end{itemize}
\textbf	Extended interface:
	\begin{itemize}
		\item Delete
		\item (Decrease/Increase)Key\\
			Delete + Add
		\item Mergable $\rightarrow$ Add, Delete\\
			Add: если реализован Merge, то реализован Add через Merge с новым элементом\\
			Delete: удаляем элемет, Merge'им его детей, и подвешиваем результат к родителю удалённого элемента
		\item Find $\O(1)$\\
			храним обратные ссылки, поддерживаем ответ по элементу, храним в массиве hash-table
	\end{itemize}
\pagebreak	

\section{K-Heap}
	Binary Heap -- частный случай K-Heap, поэтому все операции знакомые по Binary Heap переносятся и на K-Heap,
	однао некоторые оценки времени отличаются.\\
	Рассмотрим операции $SiftUp$ и $SiftDown$:\\
	\begin{center}
		 \begin{tabular}{|c|c|c|}
		 \hline 
		 Время работы & \textbf{SiftUp}                                  & \textbf{SiftDown} \\ 
		 \hline 
	 	 Binary Heap    & $\O(\log_2 n)$ & $\O(\log_2 n)$ \\ 
		 \hline 
		 K-Heap             & $\O(\log_k n)$  & $\O(k\log_k n)$ \\ 
		 \hline 
		 \end{tabular}
	 \end{center} 

	Обратите вниение на время работы операции $SiftDown$ у K-Heap -- $\O(\frac{k}{log_k n})$. Почему так происходит? При просеивании вниз необходимо просмотреть
	 всех детей число которых равно~$k$.\\
	
\textbf{	Построение кучи на массиве без использования дополнительной памяти (Inplace)}\\
	
		Удобнее всего k-ичную кучу хранить в виде массива $A[0..N-1]$, у которого нулевой элемент $A[0]$ — элемент в корне, а потомками элемента $A[i]$ являются $A[2i + 1]…A[2i + K]$. Соответственно, отец элемента $A[i]$ -- это элемент $A[\frac{i-1}{k}]$.\\
			
	\textbf {Построение K-Heap за  $\O (n)$ и доказательство времени построения}\\
	
Дан массив $A[0..N-1]$ Требуется построить K-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива — сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента $SiftUp$. Временная оценка такого алгоритма $\O(n\log n)$. Однако можно построить кучу еще быстрее — за $\O(n)$.\\

Представим, что в массиве хранится дерево ($A[0]$ -- корень, а потомками элемента $A[i]$ являются $A[ki + 1]$…$A[ki + k]$). Сделаем $SiftDown$ для вершин, имеющих хотя бы одного потомка: от $\frac{N}{K}$ до $0$,— так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.\\

	\textbf{Почему на выходе мы получим кучу:}\\

При вызове $SiftDown$ для вершины, ее поддеревья являются кучами. После выполнения $SiftDown$ эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех $SiftDown$ получится куча.\\

	\textbf{Доказательство времени работы за $\O(n)$:}\\

Число вершин на высоте $h$ в куче из $N$ элементов не превосходит $\lceil\frac{N}{K^h}\rceil$ . Высота кучи не превосходит $\log_k N$. Обозначим за $H$ высоту дерева, тогда время построения не превосходит $\sum^H_{h=1}\frac{N}{K^h}\cdot K\cdot h = N\cdot K\sum^H_{h=1}\frac{h}{K^h}$\\
  
Докажем вспомогательную лемму:\\

	\textbf{Лемма:} \\

				$\sum^{\infty}_{h=1}\frac{h}{K^h} = \frac{K}{(K-1)^2}$\\
		
	\textbf{Доказательство леммы:}\\

			Обозначим  $\sum^{\infty}_{h=1} \frac{h}{K^h} = S$. Заметим, что $\frac{n}{K^n} = \frac{1}{K}\cdot \frac{n-1}{K^{n-1}}+\frac{1}{K^n}$. \\
  		    $\sum^{\infty}_{h=1} \frac{1}{K^h}$ -- это сумма бесконечной убывающей геометрической прогрессии, и она равна 
  		    $\frac{\frac{1}{K}}{1-\frac{1}{K}}=\frac{1}{K-1}$. 					Получаем  $S=\frac{1}{K}\cdot S+\frac{1}{K-1}$, откуда  $S=\frac{K}{(K-1)^2}$.
			Подствляя в нашу формулу результат леммы, получаем $N\cdot (\frac{K}{K-1})^2 \leq 4 \cdot N = \O(n)$.\\



	
\pagebreak
\section{Leftist heap}

Левосторонняя, левацкая куча (Leftist heap) — двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи (heap order).\\
Свободной позицией назовем место в дереве, куда может быть вставлена новая вершина. Само дерево будет являться свободной позицией, если оно не
 содержит вершин. Если же у какой-то внутренней вершины нет сына, то на его месте — свободная позиция.\\

Обозначим за $d(v)$ расстояние вниз от вершины $v$ до ближайшей свободной позиции в поддереве, а за $size(v)$ число вершин в поддереве с вершиной $v$. Тогда для
для левацкой кучи выполняется следующее:
\begin{itemize}
\item $d(l[v]) \geq d(r[v])$ -- по определению левацкой кучи
\item $\log_2 size(v) \geq d(v)$ --  если бы все свободные позиции были на глубине более логарифма, то мы получили бы полное дерево с количеством вершин более $n$
\end{itemize}

Если для какой-то вершины это 1 условие не выполняется, то это легко устраняется: можно за $\O(1)$ поменять местами левого и правого ребенка, что не повлияет на порядок кучи.\\


\textbf{Merge(x, y):} // $x, y$ — корни двух деревьев
	\begin{enumerate}
		\item	if $(x = \emptyset):$ return $y$
		\item	if $(y = \emptyset):$ return $x$
		\item	if $(y.key < x.key):$  $swap(x, y)$\\
		 // Воспользуемся тем, что куча левосторонняя. Правая ветка — самая короткая\\ 
		 //и не длиннее логарифма. Пойдем направо и сольем правое поддерево с вершиной $у$.
		\item  $x.right = merge(x.right, y)$\\ 
	    // Могло возникнуть  нарушение левостороннести кучи
		\item if $(d(x.right) > d(x.left)):$  $swap(x.left, x.right)$
		\item $d(x) = min(d(x.left), d(x.right)) + 1$\\
  		// пересчитаем расстояние до ближайшей свободной позиции
		\item return $x$\\
	   // Каждый раз идем из уже существующей вершины только\\
	   // в правое поддерево — не более логарифма вызовов (по лемме)\\
		\end{enumerate}

$Time \leq d(Heap_2) + d(Heap_1) + \O(\log n)$

\pagebreak
\section{Skew heap}
	Вспомним левацкую кучу. Теперь давайте откажемся от требования, что $d(v.left) > d(v.right)$\\
	
	\textbf{Merge}
	
	\begin{enumerate}
		\item if $(x_1 > x_2)$ $swap(x_1, x_2)$
		\item $R = Merge(R, heap_2)$
		\item $swap(L, R)$
	\end{enumerate}
	
	Мы получили кривую кучу или Skew heap.\\	
	
	\textbf{Утверждение:} $Merge$ работает амортизированно за $\O(\log n)$\\
		 
	\textbf{Доказательство:}\\
	
	Пусть $\varphi$ -- количество правых тяжёлых детей (тяжёлым назовём ребёнка, если размер его поддерева больше половины всей кучи).\\
	
	Рассмотрим два случая:\\

		1) Пусть $Merge$ спускался вправо только в лёгкого сына, тогда было совершено менее $\log n$ шагов, т.к. cкаждым шагом размер поддерева уменьшался хотябы в 2 раза. За 1 вызов $Merge$ в этом случае   увеличилось не более чем на $\log n$ (каждый шаг весит не более, чем 1 по результатамswap -- a).\\
		
		2)Мы можем увеличить количество правых тяжёлых детей.\\
		
	\textbf{Утверждение:} Когда мы переходим в правого сына  $\varphi$ уменьшается на 1\\
		
	\textbf{Доказательство:}\\
		
		Так происходит из-за того, что мы делаем $swap$. Мы меняем левого и правого детей местами, тогда тяжёлым становится левый сын, а количество правых тяжёлых уменьшается на 1.\\

		Изначально  $\varphi_0 = 0$, мы предполагаем, что у нас каждая куча состоит из 1 элемента.
$\varphi = \varphi^+ + \varphi^- \geq 0$ , где $\varphi^+$  -- суммарное количество увеличений $\varphi$ , а $\varphi^-$  -- суммарное количество уменьшений $\varphi$. Отсюда следует, что  $\varphi^+ \geq \varphi^-$, $\varphi^+ \leq M\log n$ , здесь и далее $M$ -- количество вызовов функции $Merge$.\\

		$Merge$ = Т + Л (сумма для тяжелых и легких детей) = Т + $\log n$.\\
 
		$\sum	 Merge = \sum T + M \log n = \varphi^- + M \log n$ .\\

Среднее арифметическое: \\

	{\large $\frac{\sum Merge}{M} = \frac{\sum T + M\log n}{M} = \frac{\varphi^-+M\log n}{M}  \leq \frac{2 M \log n}{M} = 2 \log n = \O(\log n)$}  , здесь мы воспользовались тем, что  
	$\varphi^- \leq \varphi^+ \leq M \log n$.

	

\pagebreak

\section{Add and Merge in $\O(1)$}

		Теперь наша цель -- получить кучу, в которой операции $Add$ и $Merge$ выполняются за амортизированное $\O(1)$, а операция $DelMin$ -- за $\O(\log n)$.\\
		Нам интересно, сколько будут вместе, в среднем, работать эти операции.\\
		Пусть $Add$ выполнилась $A$ раз, $Merge$ -- $M$ раз, $DelMin$ -- $D$ раз, тогда:
	\begin{flushleft} $Time \leq A + M + D(\log n)$.	\end{flushleft}
	
	\begin{enumerate}
		 \item Пусть у нас есть структура, которая может делать:
		\begin{itemize}
			\item $Add$, $Merge$, $DelMin$ за $\O(\log n)$ 
			\item $Build$ за $\O(n)$ (строит кучу от $n$ элементов)
		\end{itemize}
			
		Мы можем получить из этой структуры такую, что $Add$ в ней будет происходить за $\O(1)$:

		Произошло $k$ раз $Add$. Перед $Merge$ и $DelMin$ вызываем $Build$  $(\O(k))$ от добавленных элементов и $Merge$ -- им получившиеся структуры (новую и старую).\\

		В среднем на каждый $Add$ мы тратим единицу $Build \rightarrow \O(1)$.	\\
		
		$Merge$ и $DelMin$ на данном этапе работают за $\O(\log n)$.
		
		$New DelMin = Build + Merge + Del$
		
		$New Merge = 2(Build + Merge) + Merge$ -- приводим каждую из двух структур к новому виду

		\item $Add$ $\O(1)$, $Merge$ $\O(\log n)$, $DelMin$ $\O(\log n)$ -- пусть структура $Q$ удовлетворяет таким условиям.
		
		\textbf{Новая цель:} $Merge$ за $\O(1)$
		
		Строим новую структуру $B$, она содержит ключ и структуру $Q$ типа $B$.
		
 		$B = \q{X, Q\q{B}}$ либо $B = null$ , $X$ -- ключ, глобальный минимум (типа $int$).
 		
		$Q$ -- это очередь элементов типа $B$, где каждый элемент -- это ключ и очередь элементов типа $B$. (Некоторая абстрактная структура). $Q$ хранит пары и сравнивает их по ключу.
		
		\textbf{Add} $(B, x)$
			\begin{enumerate}
				\item[1.] return $Merge (B, new B (x, null))$
			\end{enumerate}
			
		\textbf{Merge}$ (B_1, B_2)$
			\begin{enumerate}
				\item[1.] if $(B_1.x > B_2.x) \colon swap (B_1, B_2)$
				\item[2.] \hspace{2em} $B_1.Q = B_1.Q.Add (B_2)$
				\item[3.] return $B$
			\end{enumerate}

		\textbf{DelMin} $(B)$ // $\q{x,B}$, $х$ -- минимум, $B$ -- все остальные
			\begin{enumerate}
				\item[1.] $\q{B_2, Q_2} = B.Q.DelMin()$
				\item[2.] return $\q{x, \q{B.x, B_2.Q.Merge(Q_2)}}$ // Присоединили $Q_2$
			\end{enumerate}
			
		\textbf{Как выглядит структура:}\\
			$\q{x, B}$\\
			$B = \q{x, Q}$\\
			$Q = \q{B2, Q2}$\\
		
		\textbf{Что получили в итоге:}
		\begin{itemize}
			\item $Add$ $\O(1)$
			\item $Merge$ $\O(1)$
			\item $DelMin$ $\O(\log n)$
		\end{itemize}			
\textbf{Замечание по поводу времени работы:}\\
Если начальная структура работала за амортизированное время, то данная тоже работает за амортизированное $\O(1)$, а если просто, то за чистое $\O(1)$.
	\end{enumerate}

\end{document}
