Кучи (15 октября 2024)

1. [15 минут] V.E.B за loglogC
   1. Сформулируем задачу: heap для целых чисел от 0 до C-1. C = 2^2k (чисел битовой длины 2^k).
   2. Интерфейс Min = O(1), Add и Del = O(k) = O(loglogC).
   3. Случаи: size = 0, size = 1, size ≥ 2, struct Heapk: { Heapk-1 a; u_map<int,Heapk-1> b; int min, size; }.
   4. Реализуем Add, пересчёт Min
   5. Реализуем ExtractMin
   
   
2. [15 минут] MinMax heap [1986, Atkinson]. Inplace. Min, Max.
   1. У нас уже была Min-Max куча: хранить две бинарных и обратные ссылки.
   2. Новая идея: чётный уровень = max, нечётный уровень = min
   3. Операции Add, ExtractMin из обычной бинарной кучей выражаются через siftUp, siftDown, поэтому пропатчим siftUp, siftDown
   4. siftUp: сперва можем свопнуться в отцом, далее прыгаем на два вверх (1/2)
   5. siftDown: берём минимального из четырёх внуков, свпопаемся, решаем конфликт с отцом (5/2)
   
   
3. [15 минут] Leftist heap [1971, Clark].
   1. merge → add, (для бинарной) extractMin.
   2. struct: l, r, x, d (ввели ссылочную структуру вместо массива)
   3. d(v) = (расстояние вниз от вершины до ближайшего ``отсутствия ребенка'') - 1 ≤ log n
   4. Левацкая (leftist): d(l[v]) ≥ d(r[v]) ⇒ d(r[v]) ≤ d(v) - 1
   5. Add(x): Merge with {x}
   6. Merge: let x.key < y.key ⇒ x.right = merge(x.right, y)
if d[l[v]] < d[r[v]] then swap(l[v], r[v])
   
   
4. [10 минут] skew heap [1986, Tarjan]
   1. Укорачиваем код merge из leftist
   2. Рассказ про лёгкие и тяжёлые рёбра, показываем, за сколько работает: k + logn
   3. Придумываем потенциал "число правых тяжёлых рёбер"
   4. (можно скипать) Альтернативный потенциал: число вершин, у которых d(r[v]) > d(l[v]).

1. [25 минут] Списко-куча
   1. Мотивация: куча должна уметь Add, Min, Merge, DecreaseKey, ExtractMin. Обычная бинарная умеет всё кроме Merge за log, Merge за log². Сегодня изучили Leftist м Skew, которые умеют всё за log. Наша конечная цель − куча Фибоначчи, которая всё кроме ExtractMin умеет за O(1), ExtractMin за O(logn).
   2. Куча, которая умеет Add за O(1), Min за O(1), Merge за O(1), DecreaseKey за O(1), ExtractMin за O(n)
   3. План, как хотим самортизировать ExtractMin
   4. Турнирные деревья
   5. Quake Куча
   
   
2. [15 минут] heap: lower bound on build
   1. build: permutation → heap. Общий способ доказательства нижних оценок: если k сравнениями мы из n! перестановок выдаём одну из H(n), то нужно log(n!/H(n)) сравнений.
   2. Док-во: пусть всего есть H(n) куч, а процедура делает не более k сравнений, она разбивает n! перестановок на 2^k классов, в одном хотя бы n!/2^k,
   после build() все они различны, все они корректные кучи ⇒ H(n) ≥ n!/2^k
   1. Сколько есть различных корректных куч? H(n) = n! / ∏ size_i = n! / n(n/2)²(n/4)⁴... Доказываем по индукции: цэшка, факторилы сократятся.

1. Бонусная часть: pairing heap [1984, Fredman & Tarjan]
   1. Список → дерево. Хранение. Pairing для extractMin (null, onlyone, ret pair(pair(0, 1), pairing(2)))
   2. Время работы. Для всех операций кроме DecreasyKey O(logn).
   3. DecreasyKey: два варианта
   4. DecreasyKey, оценки: Omega(loglogn) [Fredman, 1999], O(2^2loglogn1/2) [Pettie, 2005], [Amr Elmasry (2009) уменьшил время до O(loglogn)]

Кучи (продолжение, которого не будет)

1. [10 минут] Недофибоначчи. Разбор домашнего задания.
   1. Решение 1: Храним список из n^1/2 кусков по n^1/2 элементов. Add: добавить в последний кусок, нужно хранить размер. Merge: у нас есть два мелких куска, сольём в один, разрешим [n^1/2..2n^1/2]
   2. Решение 2: Храним список кусок размера ≤n^1/2. Add и Merge = соединить списки. ExtractMin − совместить слишком мелкие списки.
   3. DecreaseKey: обратная ссылка на элемент + уменьшили его, уменьшили минимум куска (но не минимум всех кусков!)
   
   
2. [20 минут] Биномиальная [1978, Vuillemin]
   1. Определяем деревья (T_n+1 = T_n + T_n), леммы про них (размер, степень, дети, глубина), определяем кучу (список деревьев различных рангов)
   2. Как хранить? {next, child, x, rank}. По ссылкам next односвязный список. Куча = список корней.
   3. Пишем add в список, join(T_n, T_n). 2D-картинка со списками.
   4. extractMin: нашли минимум, удалили из списка; вызвали merge для списка корней и списка детей.
   5. merge: используем vector<Node*> roots[maxLog], складываем туда все корни. Время работы = Roots + maxLog.
   6. Add и Merge за O(1) (ленивое добавление, слияние)
   7. Пишем Build за O(n) = n * Add, важно показать, как он выглядит внутри.

1. [40 минут] Фибоначчи [1984, Fredman & Tarjan]
   1. Описание кучи без decreaseKey: биномиальная куча с Add и Merge за O(1)
   2. decreaseKey: алгоритм (отрезаем себя и или помечаем отца, или рекурсивно идём в него)
   3. Доказательство: лемма про числа фибоначчи F_n = 1 + F_n-2 + F_n-3 + F_n-4..., фибоначчиевы деревья Size_n ≥ F_n.
   4. Доказательство: интуиция с числом единиц, ранг дерева, правильный инвариант