Изменения
Нет описания правки
# Предложите реализацию очереди, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в очереди". Амортизированная стоимость всех операций должна быть $O(1)$.
# Можно ли реализовать два стека на очереди (ограничений на время выполнения операций нет)?
# В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Какое оптимальное асимптотически $d$ следует выбрать?
# В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Время выполнения decreaseKey - $C_1 \log n$, а extractMin - $C_2 d \log n$. Какое $d$ следует выбрать?
# Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?
# Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истиное $O(1)$, а амортизированная стоимость остальных операций не поменялась?
# Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Ограничений на число деревьев одного ранга нет. Разработайте операции merge и extractMin для тонких куч. Амортизированная стоимость операции extractMin должна быть $O(\log n)$. Амортизированная стоимость операции merge должна быть $O(1)$.
# Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
# Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
# Ускорение extractMin. Докажите, что в тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
</wikitex>
