Изменения
Нет описания правки
# Тонкие кучи. Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
# Ускорение extractMin. Докажите, что в фибоначчиевой или тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
# Продемонстрируйте последовательность операций с фибоначчиевой кучей, при выполнении которой заключительная операция decreaseKey выполняется за истиное $\Omega(n)$
# Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее)
# Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
# СНМ на списках с ранговой эвристикой. Будем хранить каждой множество в СНМ как список его элементов, каждый элемент знает голову, голова знает хвост. Тогда объедиенение двух списков происходит за время пропорциональное длине одного из них. Докажите, что если каждый раз добавлять меньший список к большему, суммарное время работы всех операций Union будет $O(n \log n)$.
# Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k ребер
# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите, что в среднем время работы get будет $O(\log n)$.
</wikitex>
