Сортировки и кучи (19 октября 2016)

  1. [15 минут] Sort: Kirkpatrick за loglogC
    1. Записать общую рекурсивную функцию
    2. Показать, где хеш-таблицы,
    3. Главная оптимизация: не передаём максимум вектора в рекурсию
  2. [15 минут] V.E.B за loglogC
    1. Сформулируем задачу: heap для целых чисел от 0 до C-1. C = 22k.
    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
− Перерыв −
  1. [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)
  2. [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])
  3. [10 минут] skew heap [1986, Tarjan]
    1. Укорачиваем код merge из leftist
    2. Рассказ про лёгкие и тяжёлые рёбра, показываем, за сколько работает: k + logn
    3. Придумываем потенциал "число правых тяжёлых рёбер"
  4. [5 минут] куча, которая умеет Add за O(1), Min за O(1), Merge за O(1), DecreaseKey за O(1), ExtractMin за O(n)