[s1 | 2024] Алгоритмы и Структуры Данных, Первеев М. В., лекция 8

• У корня должно быть k детей, ранги которых должны быть устроены определенным образом.  

• Введено понятие дерева со звездочкой, где вырезается один сын.  

• Выначивая куча - это набор выначивых деревьев, где значения родителей всегда меньше значений детей.  

• Куча хранится как биномиальная куча с двусвязным списком корней.  

• Указатель на минимум хранится отдельно.  

• Обсуждаются операции мерш, гетмин и экстракт мин.  

• Операция экстракт мин удаляет корень с минимумом и объединяет его детей в новый корень.  

• Вводится операция консоли дейт для объединения деревьев с одинаковым рангом.  

• Объединяются деревья с одинаковым рангом, создавая новые деревья с большим рангом.  

• Используется массив для хранения ссылок на деревья с одинаковым рангом.  

• Операция выполняется за логарифмическое время.  

• Потенциал структуры данных - это количество деревьев.  

• Операция экстракт мин увеличивает количество деревьев на логарифм.  

• Амортизированное время работы операции - логарифм.  

• Вершины со звездочкой используются для декрески.  

• Декрики выполняются легко, без раздувания.  

• Уменьшение ключа в вершине может привести к проблемам, поэтому используется другой подход.  

• Если вершина корень, просто меняем ключ.  

• Если вершина не корень, обрезаем ребро и отправляем сына в список корней.  

• Если у вершины нет сына, добавляем звездочку и уменьшаем ранг.  

• Если вершина уже была со звездочкой, добавляем еще одну звездочку.  

• Если вершина корень, снимаем звездочку и уменьшаем ранг.  

• Если вершина не корень, отправляем ее в список корней и снимаем звездочку.  

• Если у родителя нет звездочки, отрезаем себя и отправляем в список корней.  

• Если у родителя есть звездочка, выпиливаем дерево и отправляем в список корней.  

• Продолжаем до тех пор, пока не найдем вершину без звездочки или корень.  

• Потенциал операции должен уменьшаться.  

• Изменяем потенциал на количество деревьев плюс два умножить на количество вершин со звездочкой.  

• Это улучшает амортизированное время операции.  

• Истинное время равно количеству рекурсивных запусков.  

• Для каждого запуска выполняем действия по удалению вершины и пересчитываем минимум.  

• Считаем количество деревьев и вершин со звездочкой до и после операции.  

• Начальный потенциал выглядел как т плюс два с.  

• Итоговый потенциал: к плюс т плюс к плюс два с минус два к минус т минус два с.  

• После упрощения получается единица.  

• Декреки работает максимально тупо: перекидываем вершину в корень и уменьшаем ключ.  

• Звездочки нужны для поддержания потенциала и остановки рекурсии.  

• Важно поддерживать, есть ли у вершины звездочка, чтобы не сломать структуру.  

• Слишком много действий может сломать структуру.  

• Слишком мало действий может не сработать оценка количества вершин.  

• Пример с бамбуком, где у всех вершин ранг 10, но это не бамбук.  

• Звездочки убираются при встрече корня со звездочкой.  

• После консолидейта все корни без звездочек.  

• Пересчет минимума после консолидейта.  

• Структура классная с точки зрения теории.  

• Память: для каждой вершины храним ранг, звездочку, указатели на братьев и минимум.  

• Биномиальная куча для улучшения памяти.  

• Обсуждение структуры данных ДСУ.  

• Операции: юнайт объединяет элементы в одном множестве и гет возвращает представителя множества.  

• Примеры использования ДСУ в алгоритмах.  

• Обсуждение простой реализации, где гет за единичку, а юнайт за логарифм.  

• Хранение множеств как векторов элементов.  

• Для каждого элемента храним номер множества.  

• При юнайте перекладываем элементы из меньшего множества в большее.  

• Амортизированное время работы юнайта - логарифм.  

• Пример с кучей, где каждое добавление - логарифм.  

• Идея: размер множества удваивается при каждом перекладывании.  

• Хранение множеств в виде деревьев.  

• При юнайте подвешиваем одно дерево к другому.  

• Представители множеств - корни деревьев.  

• Функция гет: проверяем корень или родитель.  

• Функция юнайт: склеиваем деревья, если они не в одном множестве.  

• Проблема: юнайт зависит от гет, что может привести к долгому выполнению.  

• Подвешиваем меньшее дерево к большему.  

• Вводим массив рангов для вершин.  

• При объединении подвешиваем дерево с меньшим рангом к дереву с большим рангом.  

• Если ранги вершин равны, увеличиваем ранг новой вершины на единицу.  

• Пример: если ранги равны, подвешиваем меньшую вершину к большей.  

• Если ранги равны, увеличиваем ранг нового корня на единицу.  

• В дереве с рангом р есть хотя бы 2 в степени р вершин.  

• Доказательство по индукции: после каждой операции юнайтед свойство сохраняется.  

• В случае объединения двух деревьев с рангами р и р', получаем дерево с рангом р + 1.  

• Ранг вершины не может быть больше логарифма.  

• Ранг родителя всегда больше ранга сына.  

• Гет и юнайт работают за логарифм, так как ранги не превышают логарифм.  

• Доказано, что гет и юнайт работают за логарифм.  

• Ранговая эвристика улучшает производительность без значительных изменений в коде.  

• Рассматривается оптимизация гет в дереве.  

• Дерево не важно, главное - корректность работы.  

• Идея: преобразовать дерево в структуру, где все вершины подвешены к корню.  

• Удаление ребер и подвешивание вершин к корню.  

• Преобразование бамбука в структуру с подвешенными вершинами.  

• Подвешивание вершин к корню для оптимизации гет.  

• Переподвешивание вершин к корню при вызове гет.  

• Изменение родителя вершины на корень.  

• Проблемы с рангами вершин после переподвешивания.  

• Введение эвристики сжатия путей.  

• Доказательство, что без рангов работает за логарифм.  

• Доказательство, что с рангами и сжатием работает быстрее, чем логарифм.  

• Введение последовательности ф большое от н.  

• Определение итерированного логарифма лок звездочка н.  

• Пример расчета итерированного логарифма для чисел.  

• Доказательство, что амортизированное время работы операции - логарифм со звездочкой.  

• Необходимость вспомогательных фактов для доказательства.  

• Введение рангов и подвешивание деревьев с меньшим рангом к деревьям с большим рангом.  

• Лемма 2: количество вершин с рангом р не превосходит n/2^r.  

• Объяснение: в каждом дереве с рангом р есть хотя бы 2^r вершин, что не превышает общее количество вершин n.  

• Введение понятия группы вершин.  

• Номер группы вершины равен итерированному логарифму её ранга.  

• Группы вершин различаются по количеству вершин в них.  

• Лемма 3: количество вершин в группе г не превосходит n/f^g, где f - функция последовательности степенных башен.  

• Объяснение: чем больше группа, тем меньше в ней вершин.  

• Доказательство: фиксируем группу и рассматриваем ранги вершин в ней.  

• Определение рангов вершин в группе.  

• Ранги вершин в группе лежат в диапазоне от f^g-1+1 до f^g.  

• Суммирование количества вершин с фиксированным рангом для всех рангов в группе.  

• Вынесение n из знаменателя и упрощение выражений.  

• Доказательство, что сумма не превосходит n/2 в степени f^g-1+1.  

• Подготовка к доказательству основной теоремы.  

• Рассматривается вызов функции гет, который проходит по вершинам дерева.  

• Вершины делятся на три типа: корень и сын корня, вершины с разной группой и вершины с одинаковой группой.  

• Подсчитывается количество вершин каждого типа для всех запросов.  

• Множество А: не более двух вершин для каждого запроса.  

• Множество Б: не более логарифма звездочки смен групп.  

• Множество Ц: максимальное количество раз, когда вершина может попасть в группу Б.  

• Вершина может попасть в группу Б, если ранг родителя увеличивается.  

• Максимальное количество увеличений рангов: разность между рангами родителя и вершины.  

• Суммирование по всем группам и вершинам.  

• Оценка сверху: сумма не больше, чем логарифм звездочки.  

• Амортизированное время работы каждого гет: логарифм звездочки.  

• На практике время работы можно считать константой.  

• Теоретические изыскания могут быть улучшены.  

• На практике время работы практически константа.  

• Подсчет прыжков для каждой вершины и группы.