\Section{Биномиальная куча}{17 октября}{Жидков Николай}


\Subsection{Определения}


Определим понятие "биномиальное дерево" рекурсивно.
\begin{Def}

Биномиальным деревом ранга $0$ или $T_0$ будем называть одну вершину.
Биномиальным деревом ранга $n+1$ или $T_{n+1}$ будем называть дерево $T_n$, к корню которого подвесили еще одно дерево $T_n$ (порядок следования детей не важен).
При этом биномиальное дерево должно удовлетворять свойству кучи (значение в вершине не больше значения в предках).
\end{Def}

Выпишем несколько простых свойств биномиальных деревьев.

\begin{Lm}
$|T_n|=2^n$
	\begin{proof}
	Индукция по рангу дерева (далее эта фраза и проверка базы индукции будет опускаться). Для $n=0$, действительно, дерево состоит из одной вершины.
	Тогда $|T_{n+1}|=|T_n|+|T_n|=2^n+2^n=2^{n+1}$. 
	\end{proof}
\end{Lm}

\begin{Lm}
$degRoot(T_n)=n$
	\begin{proof}
	$degRoot(T_{n+1})=degRoot(T_n)+1=n+1$
	\end{proof}
\end{Lm}

\begin{Lm}
Сыновьями $T_n$ являются деревья $T_0, T_1, .. , T_{n-1}$.
	\begin{proof}
	К сыновьям $T_n$ добавляется еще одно дерево $T_n$, поэтому для $T_{n+1}$ сыновьями будут старые деревья $T_0, .., T_{n-1}$ и новый $T_n$.
	\end{proof}
\end{Lm}

\begin{Lm}
$Depth(T_n)=n$
	\begin{proof}
	$Depth(T_{n+1})=max(Depth(T_n), 1 + Depth(T_n))=1+Depth(T_n)=1+n$
	\end{proof}
\end{Lm}

Теперь определим понятие "биномиальная куча".

\begin{Def}
Биномиальная куча - список биномиальных деревьев различного ранга.
\end{Def}


\Subsection{Реализация функций для биномиальной кучи}

\Subsubsection{Как хранить?}

Мы будем хранить каждую вершинку кучи как структуру, у которой есть поля $next, child, x, rank$.
Последние два параметра - это значение, хранимое в вершине и ранг дерева, соответсвующего наше	 вершине.
Вместо того чтобы хранить список всех детей, мы будем хранить только указатель на первого ребенка (поле $child$).
Также будем хранить указатель на следующую вершину-соседа (поле $next$).
Таким образом, чтобы проитерироваться по детям вершины, надо взять вершину по указателю $child$, и переходить по указателям $next$, пока дети не закончатся.

\begin{code}
struct Node{
	Node *next, *child;
	int x, rank;
};
\end{code}

\Subsubsection{Append}

Пусть $a$ - это первая вершина списка детей какой-то вершины (например, $p$).
Эта функция добавляет в список детей  вершины $p$ вершину $b$ (гарантируется, что $b$ не лежит ни в чьем списке детей).

\begin{code}
void Append(Node *&a, Node *b){
	b -> next = a;
	a = b;
}
\end{code}

Как это работает?
 
Вначале мы говорим, что у вершины $b$ есть новый сосед - вершина $a$.
Теперь $b$ - это указатель на начало списка из вершины $b$ и детей $p$.
Присвоение в $a$ значения $b$ нужно, чтобы $a$ оставалась вершиной-началом списка детей $p$.
Мы передаем $a$ в функцию через \&, что гарантирует, что все измения с $a$ также произойдут и с переменной, от которой вызывали функцию. 

\Subsubsection{Join}

Эта функция подвешивает дерево $T_n$ к дереву $T_n$ (очень важно, что они одинаковых рангов!), сохраняя свойство кучи.

\begin{code}
Node *Join(Node *a, Node *b){
	if (a -> x > b -> x)
		swap(a, b);
	Append(a -> child, b);
	(a -> rank)++;
	return a;
}
\end{code}

Как это работает?
В данной функции $a$ и $b$ - это корни (на самом деле указатели на корни, но я буду опускать это слово) двух деревьев.
После операции $swap$ в $a$ будет корень дерева с меньшим значением. 
После мы добавляем $b$ в список детей $a$ с помощью уже имеющейся функции $Append$ и увеличиваем ранг $a$ на единицу. 

\Subsubsection{ExtractMin}

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

\begin{code}
pair<Node *, int> ExtractMin(Node *a){
	Node **m = &a;
	for (Node **p = &a; *p; p = &((*p) -> next)){
		if ((*p) -> x < (*m) -> x)
			m = p;
	Node *res = *m;
	*m = (*m) -> next;
	return <UnionHeaps(a, res -> child), res -> x>;
}
\end{code}

Как это работает?

Что нам надо сделать? Нам надо пробежать по всем деревьям, и так как для любого дерева выполнено свойство кучи, достаточно рассмотреть значение в его корне.
Далее надо взять минимальное из рассмотренных значений, и удалить вершину, которой соответствет этот минимум.
В нашей функции будем поддерживать переменную $m$ такую, что $m=$\&$(t $->$ next)$, где $t$ - это вершина, для которой сосед справа и есть минимум.
Другими словами, в переменной $m$ хранится как-бы указатель на вершину, которая является минимумом, но хранится он как адрес в памяти, где лежит значение $t$->$next$ ($t$ - это левый сосед минимума), поэтому когда мы возьмем (*$m$), то получим (*(\&($t$->$next$))) = $t$->$next$, то есть минимум, что и требовалось.
Переменная $p$ - это то же, что и $m$, только там хранится не минимум, а текущее дерево. 
Цикл $for$ в коде - это цикл, перебирающий корни всех деревьев (*$p$ - текущий корень).
Обновление ответа в цикле - обычное сравнение. 
Далее в $res$ сохраняется наш минимум.
Пото мы делаем $*m=(*m)$->$next$, что равносильно $*($\&$(t$->$next))=(*($\&$(t$->$next)))$->$next \Leftrightarrow t $->$ next = t $->$ next $->$ next$.
В результате теперь $t$ ссылается не на $m$, а на вершину, на которую раньше ссылался $(t$->$next)$, то есть наш минимум.
Таким образом мы удалили минимум из списка корней деревьев, оставив все связи корректными.
В итоге у нас остался список детей, оставшихся от минимума, которые надо прилепить к нашей куче.
Это делает функция $UnionHeaps$, которая объединяет две кучи. О ней и пойдет речь в следующей главе.

P.S. Удаление минимума можно делать проще (в плане понимания), если хранить не только правого соседа, но и левого. 
Минус в том, что при таком подходе код получиться более громоздким.

\Subsubsection{UnionHeaps}

Принимает на вход принимает указатели на кучи (на их начала), возвращает указатель на новую кучу.
Для этого заведем массив векторов $v$, и в $v[i]$ будем хранить все деревья ранга $i$ из обеих куч.
Данная функция сначала заполняет массив $v$, а потом вызывает функцию $getHeap$, которая по массиву $v$ строит новую кучу.

\begin{code}
Node* UnionHeaps(Node *a, Node *b){
	Have(a);
	Have(b);
	return getHeap();
}
\end{code}

Замечание $1$. Обнулять массив $v$ не надо, так как наша куча будет устроена так, что к моменту вызова $UnionHeaps$ массив $v$ и так будет пуст.
Замечание $2$. Просто приписать один список корней к другому нельзя, так как по определению кучи, все деревья должны быть разных рангов.
\Subsubsection{Have}

Функция, распихивающая деревья по векторам, соответсвующим их рангам.

\begin{code}
void Have(Node *a){
	for (;a;a = a -> next)
		v[a -> rank].push_back(a)
}
\end{code}

\Subsubsection{getHeap}

Как уже было сказано, по массиву $v$ строит новую кучу.
Для этого делаем следующее.
Будем идти по списку деревьев от меньших рангов к большим.
Если в данный момент мы встретили два дерева одинакого ранга, то сольем их в одно дерево с помощью функции $join$.
При этом новое дерево будет иметь ранг, на один больше, чем у деревьев, из которых оно было получено.
Добавим его в соответсвующий вектор в массиве $v$.

Можно заметить, что из деревьев одного ранга получаются деревья большего ранга, поэтому если мы закончили обработку вектора $v_i$, то для всех элементов массива от $0$ до $i$ уже все корректно и не испортится.
В итоге мы получим массив $v$, в котором не может быть деревьев одинакового ранга (иначе мы бы применили к ним $join$), а следовательно, получили корректную биномиальную кучу.

\begin{code}
k = log_2 (N+1); 
node *getHeap(){
	node *res = NULL;
	for (int i = 0; i < k; i++){
		while ((int)v[i].size() >= 2){
			v[i + 1].push_back(join(v[i][(int)v[i].size() - 1], v[i][(int)v[i].size() - 2]));
			v[i].pop_back();
			v[i].pop_back();
		}
		if ((int)v[i].size()){
			if (res == NULL)
				res = v[i][0];
			else
				res -> next = v[i][0];
			v[i].pop_back();
		}
	}
	return res;
}
\end{code}

Здесь $N$ - максимальное количество вершин, которое может быть в куче.
Так как размер $T_n$ это $2^n$, то ранг дерева можно оценить сверху двоичным логарифмом от количества вершин.
Собственно, $k$ - это и есть максимальный ранг, который может встретиться в куче.
Еще можно заметить, после завершения итерации цикла вектор $v_i$ становится пустым, то есть в конце массив $v$ полностью опустеет.

Комментарий по коду. Мы перебираем ранги от меньших к большим. 
Когда мы стоим на ранге $i$, мы делаем $join$ двух деревьев этого ранга пока можем (для удобства все время берем два последних дерева).
Если в конце осталось одно дерево ранга $i$, то добавим его в ответ.

\Subsection{Общие слова про стандартную реализацию биномильной кучи}

Такая реализация кучи не дает никаких преимуществ по сравнению с ранее изученными.
Основные операции $ExtractMin$ и $Add$ (добавление одного элемента, реализуется как $UnionHeaps$ от кучи и нового элемента) используют в себе функцию $UnionHeaps$, которая работает за $O(\log n)$ (доказательство будет ниже), поэтому в такой реализациии биномиальная куча не представляет особого интереса.

\Subsection{Быстрый Add или как сломать биномиальную кучу, чтобы она заработала быстрей}

Переделаем наше определение биномаильной кучи, разрешив ситуацию существования нескольких куч одного ранга.

Сделаем новую функцию $merge$, которая сливает две кучи.
Для этого будем хранить кучу не как указатель на начало, а как пара указателей: на начало списка и на конец.
Теперь написать $merge$ легко - нам надо прицепить начало одной кучи к концу другой.
Такой $merge$ работает за $O(1)$.
$Add$ (добавление одного элемента) выражается через $merge$ (сливаем старую кучу и новый элемент (на самом деле кучу из одного дерева $T_0$)).
Поэтому $Add$ теперь тоже работает за $O(1)$.
При этом в $ExtractMin$ все еще будем вызывать $UnionHeaps$.

\Subsection{Время работы новой реализации с быстрым Add}

Покажем, что несмотря на то что $Add$ стал работать быстрее, $ExtractMin$ все еще работает за амортизированный $O(\log n)$.

Пусть в массиве $v$ лежит всего $\alpha$ деревьев.
Покажем, что тогда суммарное время работы всех $join$ при выполнении $getHeap$ это $O(\alpha)$ с помощью амортизационного анализа.

Пусть $\varphi$ = $ v.size()$, где $v.size()$ - это суммарное количество деревьев в массиве $v$.
Тогда рассмотрим, что происходит при операции $join$.
Он работает за $O(1)$, поэтому считаем $t_i=1$.
При этом два дерева удалились, и появилось одно новое, то есть $\Delta \varphi=-1$, следовательно, $a_i=0$.
Суммарно потенциал изменился ровно на $v.size()$, так как массив $v$ полностью опустел.
Итого $T=A-(\varphi_{end}-\varphi_{beg}) \leqslant 0 - (0 - v.size()) = \alpha$.

Теперь с помощью амортизационного анализа оценим время работы $ExtractMin$.
Пусть на момент вызова $ExtractMin$ в куче было $\alpha$ деревьев.
Возьмем $\varphi = 3roots$, где $roots$ - количество деревьев в куче.
Заметим, что всего за $ExtractMin$ потенциал изменился с $3roots$ до $3\log n$ (или меньше), так как в новой куче будет не более $\log n$ деревьев.

Оценим реальное время работы.
$ExtractMin$ работает за пробег по массиву корней, то есть за $\alpha$.
$Have$ пробегает по первому списку корней (это $\alpha$), а потом по списку детей удаленного минимума (не более чем $\log n$, так как в дереве степень вершины не может больше $\log n$, так как у вершины только различные сыновья, то размер самого большого это $2^{rank}$, поэтому если есть сын с рангом, большим, чем $\log$, то размер этого сына больше $n$).
$getHeap$ работает за $\log n$(итерация по всем степеням) + $\alpha$ на все $join$.
Получаем, что $a_i=t_i+\Delta \varphi = 3\alpha+2\log n + (3\log n - 3\alpha) = O(\log n)$.
Суммарное изменение потенциала это $O(n)$ (количество корней не может измениться больше, чем на $n$).
Итого получили амортизационный логарифм на $ExtractMin$. 
