\documentclass[12 pt]{article}

\ifx\pdfoutput\undefined
\usepackage{graphicx}
\else
\usepackage[pdftex]{graphicx}
\fi

\usepackage[margin = 1cm]{geometry}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
%\usepackage{oberdiek}
\usepackage[russian]{babel}
\usepackage{amsthm, amsmath, amssymb}
\usepackage{xcolor}
%\usepackage{ upgreek }
\usepackage{listings}
\lstset{
  language=C++,
  tabsize=2,
  belowcaptionskip=1\baselineskip,
  breaklines=true,
  xleftmargin=1cm,
  escapechar=|,
  showstringspaces=false,
  basicstyle=\footnotesize\ttfamily,
  numbers=left,
%  commentstyle=\footnotesize\ttfamily
  commentstyle=\usefont{T2A}{fcr}{m}{sl}
}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\SO}{\Righarrow}
\newcommand{\EQ}{\Leftrightarrow}

% \varphi - функция потенциала
% \to - стрелочка вправо
%hspace{ length } - пробел длины length hspce* - даже в начале строки

\begin{document}
	\begin{center} {\large {\bf PairingHeap} - амортизированное время операции DelMin за $\O(\sqrt{n})$}	\end{center} 	
	
	Рассмотрим немного неверный Pairing (доказательство амортизированного времени работы DelMin (с упрощением до DullPairing) всё равно катит).  \\
	\hspace*{0.5cm}Функция Pairing из $n$ корней деревьев, хранящихся в списке, делает 1 корень, объединяя элементы. Сначала объединяет два последних элемента. А результат каждого объединения объединяет (Merge) со следующим элементом списка. При Pairing амортизированное время работы DelMin равно $\O( \log n)$.
	\begin{center} \includegraphics[width=7in, keepaspectratio]{img/PairingHeap_after.jpg} \end{center}	
	\hspace*{0.5cm} Рассмотрим более простую процедуру: DullPairing. Докажем, что при применении DullPairing амортизированное время работы DelMin $\O( \sqrt n)$. Она разбивает n элементов на произвольные пары, объединяя их (Merge) и получая $\lceil n/2 \rceil$ элементов. Это мы будем использовать в доказательстве того, что амортизированное время работы алгоритма DelMin на рассматриваемой куче равно $\sqrt{n}$.\\ 
	\begin{center} \includegraphics[width=7in, keepaspectratio]{img/DullPair_after.jpg} \end{center}
	
	\underline{Замечание:} если необходимо разбить нечётное количество элементов, то последний останется без пары. \\ 	Пример: (0 1) (2 3) (4 5) 6\\
	Для доказательства времени работы с помощью метода потенциалов введем следующие обозначения: 
	\begin{itemize}
		\item $t_i$ - реальное время работы операции. 
		\item $a_i$ - амортизированное время работы операции. 
		\item $\varphi$ - потенциал. 
	\end{itemize}
	\hspace*{0.5 cm} Тогда $a_i = t_i + \Delta \varphi$, где $\Delta \varphi = \varphi_{i + 1} - \varphi_i$. Заметим, что в таком случае верна следующая формула: $\sum \frac{a_i}{m} = \sum \frac{t_i}{m} + \frac{ \varphi_m - \varphi_0}{m}$, где m -  количество операций. В этой формуле $\sum \frac{t_i}{m}$ - среднее время работы. Т.к. $\varphi_m$ и $\varphi_0$ ограничены сверху константой, то если мы докажем, что $a_i \le \sqrt{n}$, можно дать оценку $\sum \frac{t_i}{m}$, которая тоже будет $\O(\sqrt{n})$ \\
	\hspace*{0.5 cm} Теперь рассмотрим алгоритм DelMin. Он включает в себя вызовы Del, работающего за $\O(1)$, \\ Merge - $\O(1)$ и Pairing - $\O(\# Roots)$. \\
	\hspace*{0.5 cm} Рассмотрим следующую функцию для $\varphi$: $\varphi = 2(\#Roots) + 2\sum_{по всем элементам} max(deg, \sqrt{n})$, где deg - степень вершины очередного элемента в списке. Найдём чему равно $\Delta \varphi_i$ - изменение потенциала при удалении этого элемента. \\
$$
	\begin{tabular}{|p{6 cm} |p{6 cm} |p{6 cm} |}
	\hline
	& \multicolumn{2}{c|}{$\Delta$(слагаемое)} \\
	\hline
	\multicolumn{1}{|c|}{название функции} & \multicolumn{1}{|c|}{2(\#Roots)} & \multicolumn{1}{|c|}{$2 \sum \max(deg, \sqrt{n})$} \\
	\hline
	\center Del & $-2$ \par Удаляем одну вершину (2 \---- это коэффициент, ''$-$'' т.к. вершин становится меньше) & $-2deg$ \par
	Из суммы всех степеней уходит степень вершины, которую удаляем  \\
	\hline
	\center Merge \par & $+2deg$ \par 
	Каждого из детей удаленной вершины заносим в список (их deg) (2 - коэффициент, ''+'' т.к. вершин становится больше)& 0 \par
	Ничего не меняется, просто добавляем вершины в список \\
	\hline
	\center Pairing \par & $- roots - deg$ \par
	$-roots-deg$ = $\frac{-2 \cdot (roots + deg)}{2}$: было $roots$ корней, после merge стало $roots + deg$, и мы уменьшаем их количество вдвое& $2 \sqrt{n}$ \par
	Теперь степень некоторых вершин увеличилась на 1. А количество вершин, для которых что-то изменилось не больше, чем $\sqrt{n}$, т.к. это могут быть только вершины, степень которых была не меньше $\sqrt{n}$(всего вершин n). \\
	\hline
	\end{tabular}
$$	
	Получаем следующую оценку для $\varphi$: $0 \le \varphi \le cn \sqrt{n}$, где с - некая константа. \\ 
	Результат: $\sum t_i = \sum a_i + \varphi_0 - \varphi_m, где \sum a_i \approx m \sqrt{n}$, a $\varphi_0 - \varphi_m \approx n \sqrt{n}$. Таким образом, среднее время работы равно $\O(\sqrt{n})$, если $n \ge m$ (если $n < m$, то этого тоже добиваются, но немного другим потенциалом, на лекции рассказано не было). \\
	
	Правильный Pairing будет в следующем конспете, а пока - вот вам картиночка!
	\begin{center} \includegraphics[width=7in, keepaspectratio]{img/Pair_after.jpg} \end{center}
	
	
	\begin{center} {\large \bf Биномиальные кучи}	\end{center} 
		
	Биномиальное дерево - это дерево, задающееся следующим рекурентным способом. \\
	\begin{center} \includegraphics[width=6in, keepaspectratio]{img/BinTree_after.jpg} \end{center}
	
	За корень биномиального дерева ранга $k$ (дерево $T_k$) подвешено соответственно $k$ биномиальных деревьев с рангами от 0 до $k-1$. \\
	\hspace*{0.5cm}Биномиальная куча - множество из $n$ элементов, разбитое на множества, с мощностями, равными степени двойки, для каждого множества строится биномиальное дерево со свойством кучи. Т.е. куча = $\O( \log n)$ деревьев, или другими словами: биномиальная куча - множество биномиальных деревьев различного ранга.
	$n = \sum 2^{k_i}$; $|T_k| = 2^k$ 
	\begin{center} \includegraphics[width=5.7in, keepaspectratio]{img/BinHeap_after.jpg} \end{center}	
	\begin{center} \includegraphics[width=5.7in, keepaspectratio]{img/ExampleBinHeap_after.jpg} \end{center}
	Операция Merge для Биномиальной кучи:
	\begin{lstlisting}
Merge (a, b) |- $\O( \log n)$|				// |сливаем деревья|
{
	for k = 0..logN						// |деревьев не может быть больше, чем $\log N$|
		if b[k] != NULL					// |проверка, есть ли дерево нужной размерности|
		for (i = k, c = b[k]; a[i] != NULL; i++)
			c = c + a[i];					// |получаем из двух $T_k$ одну $T_{k+1}$|
			a[i] = NULL;					// |удаляем ссылку на переписанное дерево|
		a[i] = c;								// |сохраняем полученное дерево|
}
	\end{lstlisting}
	\begin{center} \includegraphics[width=6in, keepaspectratio]{img/Merge_after.jpg} \end{center}

	\begin{center} {\large \bf Фибоначчиева куча}	\end{center} 
		
	Куча Фибоначчи - список биномиальных деревьев со свойством кучи (не обязательно различного ранга). \\
	Позволяет выполнять следующие операции:
	\begin{itemize}
		\item Merge за O(1)
		\item Add за O(1)
		\item DelMin за O(logn)
		\item GetMin за O(1)
		\item DecreaseKey за O(1)
	\end{itemize}
	\begin{center} \includegraphics[width=6in, keepaspectratio]{img/FibHeap_after.jpg} \end{center}
	\begin{center} \includegraphics[width=6in, keepaspectratio]{img/end_after.jpg} \end{center}
	
	
%	$\delta
%	\varphi_0 \to \varphi_1 \to \dots \to \varphi_m\\$
%	\underline{Def:} \\
	

\end{document}
