Тренировки по алгоритмам 3.0. Лекция 2: «Очереди, деки и приоритетные очереди»
Вставка
- Опубліковано 16 лют 2023
- Подробнее о Тренировках по алгоритмам 3.0: yandex.ru/yaintern/algorithm-...
Домашнее задание станет доступно после завершения лекции:
- для дивизиона А: contest.yandex.ru/contest/45469
- для дивизиона В: contest.yandex.ru/contest/45468
Спасибо за работу !
02:42 01 Очередь
19:42 02 Дек
35:20 03 Приоритетная очередь (куча, пирамида)
1:28:28 Трансляция завершина
Лампа! Спасибо:))))
1:28:24 лампочка
1:12:30 Как я понимаю, тут идёт речь о реализации через дек + словарь, в котором ключи - данные элементы, а значения - ссылки на эти элементы в деке. Тогда мы можем добавлять в концы и удалять элемент из любого места за константное время.
в куче вместо переменной son можно использовать baby
Читаю queue, как квэвэ) По аналоги с квэ в question, наверное)
55:27 ГРЯЗНЫЙ ХАК
Скиньте ссылку на чат, на сайте ссылка устарела
как ваше решение для задачи медиана окна будет работать для повторяющихся элементов
На вопрос "чем куча лучше bst" лектор вроде бы забыл упомянуть одно из главных достоинств кучи, что амортизировано insert работает за O(1) (со скрытой константой 2) по тем же соображением почему хипифай работает за O(n) (если кучу строить снизу, а не сверху) (элемент с большей вероятностью окажется на нижних слоях, потому с каждом подъёмом на уровень выше кол-во элементов уменьшается вдвое)
Ну и ещё в некоторых случаях имеет место d-ary heap, когда insert-'ов много больше, чем extract'ов, довольно экзотический случай, когда мы много раз инсертим, совсем чуть-чуть экстрактим, а потом просто разрушаем кучу с более ненужными нам элементами. По понятным причинам у неё медленее sift down - d * log(d)(n), но быстрее sift up - log(d)(n) - первая скобочка основание
Ну и насчёт прибора вроде (если я правильно понял) намудрили, вроде бы там достаточно просто экспоненциального сглаживания - довольно простая и тупая, но эффективная штука, главное подобрать альфа (коэф. сглаживания) правильный
Слишком понятно. Лектор, похоже, недавно в Яндексе.
Не поверишь, насколько он там давно))
@@Fukurokouji_1337, не поверю.
Только что нашёл прошлогоднее кино, где Михаил прямо говорит - он не работает в Яндексе, а является преподователем в ВШЭ.
Односвязный список с указателем на хвост идеален для реализации простой очереди. Ничего лишнего.
Зачем двусвязный-то?
Читал про heap у Кормена и ничего не понял. Здесь все супер понятно!
Короче Кормен точно не для новичков😅