\Section{Кучи}{9 октября}{Татьяна Белова}
	\Subsection{Доказательство Skew Heap.} 
	
	Назовем ребенка вершины тяжелым, если размер его поддерева строго больше половины размера поддерева вершины. 
	
	Пусть $\phi$ - количество правых тяжелых детей. Заметим, что у каждой вершины не более одного тяжелого ребенка. 
	
	Посчитаем, сколько раз мы спустились в тяжелого правого сына. Наш путь мог проходить через легкие и тяжелые вершины. Заметим, что легких вершин на пути могло быть не больше $\log n$, так как при переходе в эту вершину размер поддерева уменьшается хотя бы в 2 раза. 
	
	Пусть тяжелых ребер на пути было $k$. Тогда $\Delta \phi = \mathcal{O}(\log n) - k$, так как каждый раз, когда мы спускаемся в тяжелого ребенка и merge-им его с чем-то, оно остается тяжелым, а, значит, когда мы сделаем swap, правый ребенок станет легким, и количество правых тяжелых детей уменьшится на 1. \\
	
	$a_i = t_i + \Delta \phi = \mathcal{O}(\log n) + k + \mathcal{O}(\log n) - k = \mathcal{O}(\log n)$ 
	
	$\phi_n - \phi_0 \le n $ \\
%	\vspace{3em}
%
%	\begin{center}
%		\includegraphics[scale=1.2]{cat.jpg}
%	\end{center}	
	
	\Subsection{Leftist*} 
	
	Заметим, что мы можем избавиться от условия $\forall v: d(l(v)) \ge d(r(v))$. Вместо этого будем спускаться в ребенка с меньшим $d$. 
	
	\begin{code}
		if (a->r->d < a->l->d) 
		a->r = Merge(a->r, b);
		else 
		a->l = Merge(a->l, b);
	\end{code}
	
	\vspace{50em}
	\Subsection{Pairng Heap.} 
		
	Pairing Heap - структура данных, которая умеет делать Add, Merge и ExtractMin за $\mathcal{O}(\log n)$, а DecKey за $o(\log n)$.
	
	Pairng Heap представляет из себя список корней нескольких деревьев, для каждого из которых выполняется свойство кучи, то есть значение в вершине не больше значения в ребенке.

	\begin{center}
		\includegraphics[scale=1.2]{belova/pairing_tree0.jpg}
	\end{center}	

	Для каждой вершины будем хранить список ее детей. Для этого будем хранить указатель на первого ребенка и для каждого ребенка указатель на следующего в списке. Также для каждой вершины будем хранить указатель на ее отца. 
	
	\begin{center}
		\includegraphics[scale=1.2]{belova/pairing_tree2.png}
	\end{center}
	
	Тогда Merge работает за $\mathcal{O}(1)$. Для этого мы просто добавляем в конец первого списка корней второй. 
	
	Add также работает за $\mathcal{O}(1)$. Для этого мы должны сделать merge имеющегося списка деревьев с новой вершиной.
	
	DecKey тоже работает за $\mathcal{O}(1)$. Мы фиктивно удаляем вершину из списка детей ее отца и добавляем ее в список корней.
	
	ExtractMin работает за k (длина списка корней) + Merge(Root, Min->child) + pairing. 
	
	Напишем функцию $Pairing$. 
	
	Эта функция получает список корней и переподвешивает вершины так, чтобы остался один корень, и при этом сохранилось свойство кучи.
	Для этого она сначала разбивает корни на пары, объединяет поддеревья в каждой паре, а затем по очереди объединяет все получившееся деревья в одно.  
	  
	\begin{center}
		\includegraphics[scale=0.8]{belova/ellipse.jpg}
	\end{center}
	
	
	Для начала напишем функцию Pair(a, b), которая получает 2 дерева, берет из них то, что с меньшим ключом, и второе привешивает к нему. 
	\begin{code}
		Pair(a, b) {
			if (a->x > b->x) swap(a, b);
			b->Next = a->Child
			a->Child = b
		}
	\end{code}
	
	Теперь напишем саму функцию $Pairing$. Сначала запускаем $Pair$ от двух корней. Потом рекурсивно получаем корень дерева, являющегося объединением остальных корней. А затем запускаем $Pair$ от двух получившихся корней и да будет нам радость.

	\begin{code}
		Pairing(a) {
			if |a| = 1 return a[0]; 
			if |a| = 2 return Pair(a[0], a[1]);
			return Pair(Pair(a[0], a[1]), Pairing(a[2:]));
		}	
	\end{code} 
	\vspace{19em}
	
	\Subsection{Van Emde Boas tree.}
	
	Пусть теперь все ключи лежат в диапазоне [0..C) \\
	Разобьем все элементы на куски по $\sqrt C$. \\
	$i$ попадает в $[i / \sqrt C]$ кусок. \\
	
	Назовем нашу структуру Heap. \\
	1) Храним $Min$. \\
	2) Для каждого $i$, $HashMap[i] = Heap(i)$. \\
	3) Храним $index$ - $Heap$ номеров непустых кусов. 
	
	Мы отдельно обрабатываем случай, когда куча состоит из одного элемента. В этом случае мы не храним $HashMap$ и $index$, а храним только $Min$.
		
	
	\begin{code}
		struct Heap {
			int Min;
			Heap *index;
			unordered_map<int, Heap*> HashMap;
			int ExtractMin();
			void Add(int x);
		};
	\end{code}
	
	Теперь напишем методы Add и ExtractMin.

	\begin{code} 
		Add(x, c) {
			if EMPTY return Heap(x);
			Heap* h = HashMap[x / sqrt(c)];
			if (h == EMPTY) index.Add(x / sqrt(c), sqrt(c));
			h->Add(x, sqrt(c));	
		}
		ExtractMin() {
			Heap* h = HashMap[index->Min];
			h->ExtractMin();
			if (h == EMPTY) index->ExtractMin();
			Min = HashMap[index->Min].Min;
			return Min;
		}
	\end{code}
	
	
	
	
	
	
	
	
	
