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