Сортировки и кучи (16 октября 2017)

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. Реализуем Del


2. [15 минут] MinMax heap [1986, Atkinson]. Inplace. Min, Max.
1. У нас уже была Min-Max куча: хранить две бинарных и обратные ссылки.
2. Новая идея: чётный уровень = max, нечётный уровень = min
3. Операции, как с обычной бинарной кучей, нужно научиться делать siftUp, siftDown
4. siftUp: сперва можем свопнуться в отцом, далее прыгаем на два вверх (1/2)
5. siftDown: берём минимального из четырёх внуков, свпопаемся, решаем конфликт с отцом (5/2)

1. [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])


2. [10 минут] skew heap [1986, Tarjan]
1. Укорачиваем код merge из leftist
2. Рассказ про лёгкие и тяжёлые рёбра, показываем, за сколько работает: k + logn
3. Придумываем потенциал "число правых тяжёлых рёбер"


3. [5 минут] куча, которая умеет Add за O(1), Min за O(1), Merge за O(1), DecreaseKey за O(1), ExtractMin за O(n)