Тренировки по алгоритмам 3.0. Лекция 2: «Очереди, деки и приоритетные очереди»

Подробнее о Тренировках по алгоритмам 3.0: yandex.ru/yaintern/algorithm-...
Домашнее задание станет доступно после завершения лекции:
- для дивизиона А: contest.yandex.ru/contest/45469
- для дивизиона В: contest.yandex.ru/contest/45468

[@IliaFilimonov]

02:42 01 Очередь 19:42 02 Дек 35:20 03 Приоритетная очередь (куча, пирамида) 1:28:28 Трансляция завершина

[@user-yz7wy3mm1h]

Спасибо за работу !

[@alexandersmirnov4274]

в куче вместо переменной son можно использовать baby

[@user-mt7lm8fv7k]

1:28:24 лампочка

[@mberdyshev]

1:12:30 Как я понимаю, тут идёт речь о реализации через дек + словарь, в котором ключи - данные элементы, а значения - ссылки на эти элементы в деке. Тогда мы можем добавлять в концы и удалять элемент из любого места за константное время.

[@meryrua3224]

Лампа! Спасибо:))))

[@misterzurg7874]

55:27 ГРЯЗНЫЙ ХАК

[@vp_arth]

Читаю queue, как квэвэ) По аналоги с квэ в question, наверное)

[@tortokaeva]

Скиньте ссылку на чат, на сайте ссылка устарела

[@alexandersmirnov4274]

как ваше решение для задачи медиана окна будет работать для повторяющихся элементов

[@floppa-fy2qh]

На вопрос "чем куча лучше bst" лектор вроде бы забыл упомянуть одно из главных достоинств кучи, что амортизировано insert работает за O(1) (со скрытой константой 2) по тем же соображением почему хипифай работает за O(n) (если кучу строить снизу, а не сверху) (элемент с большей вероятностью окажется на нижних слоях, потому с каждом подъёмом на уровень выше кол-во элементов уменьшается вдвое) Ну и ещё в некоторых случаях имеет место d-ary heap, когда insert-'ов много больше, чем extract'ов, довольно экзотический случай, когда мы много раз инсертим, совсем чуть-чуть экстрактим, а потом просто разрушаем кучу с более ненужными нам элементами. По понятным причинам у неё медленее sift down - d * log(d)(n), но быстрее sift up - log(d)(n) - первая скобочка основание Ну и насчёт прибора вроде (если я правильно понял) намудрили, вроде бы там достаточно просто экспоненциального сглаживания - довольно простая и тупая, но эффективная штука, главное подобрать альфа (коэф. сглаживания) правильный

[@vp_arth]

Односвязный список с указателем на хвост идеален для реализации простой очереди. Ничего лишнего. Зачем двусвязный-то?

[@xewuss3750]

Слишком понятно. Лектор, похоже, недавно в Яндексе.

[@Fukurokouji_1337]

Не поверишь, насколько он там давно))

[@xewuss3750]

@@Fukurokouji_1337, не поверю. Только что нашёл прошлогоднее кино, где Михаил прямо говорит - он не работает в Яндексе, а является преподователем в ВШЭ.

[@slowpoke7785]

Читал про heap у Кормена и ничего не понял. Здесь все супер понятно! Короче Кормен точно не для новичков😅