\Section{Кучи}{9 октября}{Владислав Кочергин}

\Subsection{$k$-heap}

$k$-ичная куча ($k$-heap, $d$-heap) - структура данных в виде дерева, в котором в каждой вершине хранится число. Для этого дерева всегда выполняются условия:

1. в каждой вершине записан минимум в своём поддереве;

2. каждая вершина либо является листом, либо имеет ровно $k$ сыновей.

$k$-ичную кучу можно хранить в массиве. 0-й элемент - корень, элементы с номерами ${ki + 1, ki+2, \ldots, ki + k}$ - сыновья вершины $i$, элемент с номером $\lfloor \frac{i - 1}{k} \rfloor$ - отец вершины $i$. Пусть для удобства реализации в несуществующих элементах лежит бесконечность.

В качестве $k$ используется обычно степень двойки, т. к. в таком случае используемые при переходе по рёбрам дерева операции умножения и деления индексов сводятся к более быстрой операции - битовому сдвигу.

~

\bfseries SiftUp и SiftDown \mdseries

Операции SiftUp и SiftDown, как и для двоичной кучи, просеивают вершину вверх/вниз до тех пор, пока она не займёт корректную позицию. Оценим время работы.

SiftUp и SiftDown в худшем случае пройдут по всей высоте дерева. Высота дерева из $n$ вершин равна $\lceil \log_k ((k-1)n + 1) \rceil$, поэтому SiftUp работает за $\mathcal{O}(\log n)$. SiftDown на каждой своей итерации делает $k$ сравнений. Поэтому SiftDown работает за $\mathcal{O}(k\log n)$.

Имея операции SiftUp и SiftDown, мы можем реализовать операции Add и ExtractMin.

\begin{code}
sift_up(i)
	while i > 0 && h[(i - 1) / k] > h[i]
		swap(h[(i - 1) / k], h[i])
		i = (i - 1) / k

sift_down(i)
	while true
		m = min_index(k * i + 1, ..., k * i + k)
		if h[i] <= h[m] break
		swap(h[i], h[m])
		i = m

add(value)
	h[end_heap] = value
	sift_up(end_heap++)

extract_min()
	res = h[0]
	h[0] = inf
	swap(h[0], h[--end_heap])
	sift_down(0)
	return res

\end{code}

\Subsection{MinMax heap}

Пусть из двоичной кучи нам нужно уметь извлекать и максимум, и минимум. Можно использовать две кучи, в одной поддержка максимума, в другой - минимума, где каждый элемент имеет ссылку на него же в другой куче. Теперь сэкономим память: объединим в одну кучу.

На нулевом уровне (в корне) будем хранить минимум в дереве.

На первом уровне будем хранить максимумы в соответствующих поддеревьях.

На втором уровне будем хранить минимумы в соответствующих поддеревьях.

На третьем уровне будем хранить максимумы в соответствующих поддеревьях.

И так далее

~

\bfseries SiftUp \mdseries

Предположим, что вершина $v$, которую нам нужно поднять, находится на уровне минимумов (противоположный случай аналогичен).

Тогда отец $v$ находится на уровне максимумов. Возможны следующие ситуации:

1. значение у $v$ больше, чем у отца: меняем их местами и делаем для $v$ из нового места обычный SiftUp с шагом $i = i / 4$. 

2. иначе делаем для $v$ обычный SiftUp с шагом $i = i / 4$.

Время работы - $\mathcal{O}(\frac{\log n}{2}) = \mathcal{O}(\log n)$.

~

\bfseries SiftDown \mdseries

Предположим, что вершина $v$, которую нам нужно спустить, находится на уровне минимумов (противоположный случай аналогичен).

Тогда дети $v$ находятся на уровне максимумов. Возможны следующие ситуации:

1. среди внуков $v$ есть те, что меньше $v$. Тогда найдём наименьшего внука $v$ и поменяем его местами с $v$. Осталось проверить - если на новом месте $v$ конфликтует со своим отцом, поменять их местами. Продолжаем SiftDown из места, где первоначально был наименьший внук $v$.

2. у $v$ нет внуков. Тогда вручную обеспечим корректность для $v$ и её детей.

На каждой итерации выполняется 5 сравнений. Время работы - $\mathcal{O}(\frac{5}{2} \log n) = \mathcal{O}(\log n)$.

~

MinMax кучу можно построить за линейное время inplace аналогично двоичной куче.

\Subsection{Leftist heap, skew heap}

Пусть в дереве каждая вершина имеет степень 0, 1 или 2. Введём для каждой вершины функцию $d(v)$ - расстояние вниз до ближайшего отсутствия вершины.

Лемма: $d(v) \le \log_2 (size+1)$.

Доказательство. Очевидно, что $size \ge 2^{d(v)} - 1 \Leftrightarrow size+1 \ge 2^{d(v)} \Leftrightarrow d(v) \le \log_2 (size+1)$.

~

Назовём левацкой кучей (leftist heap) структуру данных в виде дерева, в котором в каждой вершине хранится число. Для этого дерева выполняются условия:

1. в каждой вершине записан минимум в своём поддереве;

2. каждая вершина имеет степень 0, 1 или 2;

3. для каждой вершины $d(left(v)) \ge d(right(v))$. Для несуществующей вершины $d$ примем равным нулю.

~

От предыдущих куч эта куча отличается возможностью быстрого слияния. Пусть EMPTY - пустая вершина: $left$ и $right$ указывают на неё же, $x = \infty$, $d = 0$.

\begin{code}
Merge(a, b) {
	if (a->x >= b->x)
		swap(a, b);
	if (b == EMPTY)
		return a;
	a->right = Merge(a->right, b);
	if (a->right->d > a->left->d)
		swap(a->right, a->left);
	a->d = a->right->d + 1;
	return a;
}
\end{code}

Время работы: на каждом шаге рекурсии $a \rightarrow d + b \rightarrow d$ уменьшается, поэтому:

 $Time \le a \rightarrow d + b \rightarrow d = \mathcal{O} (\log n)$.

~

\bfseries Скошенная куча (Skew heap) \mdseries

Уберём условие $d(left(v)) \ge d(right(v))$. В функции Merge уберём 7 и 9 строки. Полученная куча называется skew heap. Merge в ней работает за амортизированное $\mathcal{O}(\log n)$, доказательство в следующей лекции.