День 8. Кучи (5 января)

Лектор: [Сережа.K]
1. Биномиальная куча
1. Определение биномиального дерева, кучи
2. Merge за O(logn)
3. Merge → Add, ExtractMin
4. Build за O(n), Add за амортизированную O(1)
5. Использование: ориентированный остов минимального веса с фиксированным корнем
2. Куча Фибоначчи
1. Add за O(1), Merge за O(1), ExtractMin за O(logn)
2. DecreaseKey за O(1), Дейкстра за O(m + nlogn)
3. Доказательство DecreaseKey: size[k] ≥ φ^k, потенциал равен R+2M.
3. Цифровые алгоритмы. Веса целые от 1 до C.
1. Алгоритм Диала за O(m + nC). Применение для вещественных весов. Разбор задачи с контеста.
2. Radix Heap, Дейкстра за O(m + nlogC)
1. В алгоритме Диала наиболее долгая операция − поиск не пустой очереди
2. Общая идея: храним бакеты вершин с расстоянием из [D, D+X), если X=1, минимум можно вытащить за O(1), иначе "разгружаем бакет"
3. При разгрузке бакета для каждой вершины v величина ind[v] "номер бакета в котором находится вершина" только убывает, поэтому суммарное время O(nlogC)
3. Two Level Radix Heap и Hot Heap, Дейкстра за O(m + nsqrt(logC))
1. Two Level: систему 2ⁱ заменим на систему kⁱ, k выберем равным loglogC, получим O(m + nlogC/loglogC)
2. Идея Hot Heap: если в бакете, который мы разгружаем не более t вершин, то построим кучу Фибоначчи и, пока количество вершин не более t, не будем разгружать.
3. t = k = 2^sqrtlogC, получим O(m+nsqrtlogC)
4. Идея на будущее для получения O(m+n(logC)^1/3)