Введение в программирование 6. Альтернативные реализации кучи: Биномиальная куча

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Лекция прочитана 7 октября 2021 года Лектор: Степанов Илья Даниилович Оператор: Мария Шкатова Монтаж: Жильцов Игорь 0:00 - Продолжение HeapSort 2:38 - Реализация Heapify 4:50 - Корректность Heapify 10:41 - Можно ли обрабатывать extractMin и insert за O(1)? 15:01 - Особенности decreaseKey 16:18 - DecreaseKey по идентификатору 29:12 - Удаление (erase) по идентификатору 34:18 - Удаление (erase) по значению 39:08 - Корректность алгоритма удаления по значения 44:18 - Обзор Фибоначчиевой кучи 49:25 - Биномиальная куча 51:21 - Биномиальное дерево 56:10 - Определение биномиальной кучи 59:39 - GetMin в биномиальной куче 1:03:33 - DecreaseKey в биномиальной куче 1:06:00 - Merge - объединение биномиальных куч 1:19:17 - Insert в биномиальную кучу 1:20:39 - ExtractMin из биномиальной кучи 1:22:30 - Корректность и асимптотика ExtractMi