Алгоритмы и структуры данных (основной поток) 6. Биномиальная куча. Амортизационный анализ

В этой лекции рассматриваются биномиальные кучи, их структура, операции (Insert, DecreaseKey, GetMin, ExtractMin), а также методы амортизационного анализа, включая пример очереди на двух стеках и метод бухгалтерского учёта. В начале лекции автор вводит тему, затем подробно описывает биномиальное дерево и биномиальную кучу, демонстрирует операции Merge и SiftUp, отвечает на вопросы студентов. В конце лекции проводится анализ амортизации с примерами и обсуждается применение метода к динамическому массиву. На последних 10 минутах камеры выключилась, что помешало комплексному восприятию, простите. 00:00:00 - Введение 00:00:05 - Анонс биномиальной кучи 00:00:18 - Задача(Erase) 00:01:03 - По указателю 00:02:51 - По значению 00:08:18 - Вопросы 00:09:07 - Почему важна корректность запросов 00:12:40 - Биномиальная куча 00:14:26 - Определение (биномиальное дерево) 00:18:04 - Определение (биномиальная куча) 00:22:26 - Merge 00:26:09 - Вопросы 00:30:58 - Insert 00:31:35 - DecreaseKey 00:31:53 - Замечание про SiftUp 00:32:59 - GetMin 00:35:10 - ExtractMin 00:39:12 - Вопросы 00:41:18 - Амортизационный анализ 00:46:39 - Пример(очередь на двух стеках) 00:50:49 - Метод бухгалтерского учёта(метод монеток) 00:54:43 - Утверждение(корректность метода) 00:58:00 - Применение метода для примера 01:00:12 - Следующий пример(динамический массив, vector в С++) 01:04:11 - Тяжёлый push_back