Кучи (14 октября 2019)

  1. Повторение V.E.B.

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

  5. [5 минут] Списко-куча
    1. Мотивация: куча должна уметь Add, Min, Merge, DecreaseKey, ExtractMin. Обычная бинарная умеет всё кроме Merge за log, Merge за log2. Сегодня изучили 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)

  6. [15 минут] heap: lower bound on build
    1. build: permutation → heap. Общий способ доказательства нижних оценок: если k сравнениями мы из n! перестановок выдаём одну из H(n), то нужно log(n!/H(n)) сравнений.
    2. Док-во: пусть всего есть H(n) куч, а процедура делает не более k сравнений, она разбивает n! перестановок на 2k классов, в одном хотя бы n!/2k,
      3. после build() все они различны, все они корректные кучи ⇒ H(n) ≥ n!/2^k
    3. Сколько есть различных корректных куч? H(n) = n! / ∏ sizei = n! / n(n/2)2(n/4)4... Доказываем по индукции: цэшка, факторилы сократятся.