Кучи (26 октября 2016)

  1. [15 минут] lower bound on build
    1. build : permutation → heap
    2. Сколько есть различных корректных куч? n! / ∏ sizei = n! / n(n/2)2(n/4)4...
    3. Пусть всего есть H куч, а процедура делает не более k сравнений, она разбивает n! перестановок на 2k классов, в одном хотя бы n!/2k элементов, что должно быть не более H.
  2. [10 минут] Недофибоначчи. Разбор домашнего задания.
  3. [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. [homework] Пишем 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. Доказательство: интуиция с числом единиц, ранг дерева, правильный инвариант