Кучи (5 ноября 2019)

  1. [10 минут] Недофибоначчи. Разбор домашнего задания.

  2. [20 минут] Биномиальная [1978, Vuillemin]
    1. Определяем деревья (Tn+1 = Tn + Tn), леммы про них (размер, степень, дети, глубина), определяем кучу (список деревьев различных рангов)
    2. Как хранить? {next, child, x, rank}. По ссылкам next односвязный список. Куча = список корней.
    3. Пишем add в список, join(Tn, Tn). 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. Доказательство: лемма про числа фибоначчи Fn = 1 + Fn-2 + Fn-3 + ..., фибоначчиевы деревья Sizen ≥ Fn.
    4. Доказательство: интуиция с числом единиц, ранг дерева, правильный инвариант