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

• Лекция посвящена структурам данных: очередям, декам и приоритетным очередям.  

• Приоритетная очередь будет реализована с помощью кучи.  

• Начнем с обычной очереди, известной как FIFO.  

• Очередь работает по принципу FIFO: первый пришел, первый вышел.  

• Основные методы: добавить элемент в конец и удалить из начала.  

• Дополнительные методы: узнать длину очереди и проверить, пуста ли она.  

• Очереди часто встречаются в компьютерах для обработки сообщений и прерываний.  

• Реализация очереди с двумя операциями: добавить и удалить.  

• Проблема: удаление элемента требует перестановки всех элементов вперед.  

• Первый вариант: копировать каждый элемент при удалении.  

• Второй вариант: изменять переменную, указывающую на начало очереди.  

• Третий вариант: использовать кольцевой буфер для экономии пространства.  

• Кольцевой буфер сворачивает очередь в кольцо.  

• При добавлении элемента он помещается в конец кольца.  

• При удалении элемента увеличивается индекс начала очереди.  

• Максимальный размер кольца определяется параметром k.  

• При достижении k элементов, индекс обнуляется.  

• Использование остатка от деления на k для автоматического обнуления.  

• Кольцевой буфер часто используется для реализации очередей.  

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

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

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

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

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

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

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

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

• Касса в кольцевом буфере указывает на индекс элемента.  

• При добавлении нового элемента, текущий элемент затирается.  

• Важно знать максимальное количество элементов в очереди.  

• Дек позволяет добавлять и удалять элементы с обоих концов.  

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

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

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

• Дек на двусвязном списке работает медленно из-за выделения памяти и указателей.  

• В C++ есть способ ускорить работу дека, используя массивы фиксированного размера.  

• Двусвязный список ускоряет работу, так как не нужно выделять память под каждый элемент.  

• Можно хранить указатели на блоки в динамически расширяемом массиве.  

• Это позволяет экономить память и обращаться по индексу.  

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

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

• Это экономит память и позволяет обращаться по индексу.  

• GC удаляет объекты, которые не используются, но имеют указатели.  

• Реализация дека на массиве требует копирования при достижении границ.  

• Чанки блоки экономят время и позволяют обращаться по индексу.  

• Блоки позволяют экономить время на выделении памяти.  

• Возможность обращаться по индексу и кэш-хиты.  

• В Python все переменные являются ссылочными типами, что позволяет хранить массивы внутри массивов.  

• Очередь с приоритетами упорядочивает события по важности.  

• Реализовать можно на массиве, но это будет медленно.  

• Куча реализует очередь с приоритетами за логарифмическое время.  

• Куча минимумов — это бинарное дерево с особым свойством.  

• Каждый узел дерева содержит полезную информацию и указатели на детей.  

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

• Дерево состоит из узлов, каждый из которых имеет не более двух детей.  

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

• Пример: основатель династии и его потомки.  

• Бинарная куча имеет не более двух детей у каждого элемента.  

• Куча заполняется по слоям, начиная с последнего слоя.  

• Каждый элемент меньше своих детей или равен им.  

• Добавление элемента в кучу: элемент добавляется в последний слой.  

• Просеивание вверх: элемент перемещается вверх по дереву, пока не будет выполнено свойство кучи.  

• Удаление минимального элемента: копирование последнего элемента и восстановление свойства кучи.  

• Куча хранится в одномерном массиве, элементы нумеруются по слоям.  

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

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

• Предок тройки равен единице.  

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

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

• Элемент добавляется в конец массива.  

• Просеивание вверх до правильного порядка или до корня.  

• Обмен элементов при необходимости.  

• Копирование удаляемого элемента в корень.  

• Просеивание вниз для удаления.  

• Три случая: нет детей, один ребенок, двое детей.  

• Не удаление элемента сразу, а просеивание вниз.  

• Оптимизация для уменьшения количества кода.  

• Удаление элемента после просеивания.  

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

• Куча лучше бинарного дерева для определения минимума и удаления.  

• В куче можно менять элементы по значению, используя словарь.  

• Пример изменения элемента с 8 на 3.  

• Использование словаря для отслеживания позиций элементов.  

• Просеивание вверх или вниз в зависимости от изменений.  

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

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

• Важность консистентного состояния для корректной работы.  

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

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

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

• Хранение видео в кэше и куче времени.  

• Обновление времени последнего обращения к элементам.  

• Удаление элементов из кэша при заполнении.  

• Пример с датчиком уровня воды и выбросами.  

• Использование медианной фильтрации для удаления выбросов.  

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

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

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

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

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

• Преобразование кучи минимумов в кучу максимумов решает эту проблему.  

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

• Пирамидальная сортировка поддерживает кучу максимумов и отсортированную часть массива.  

• Превращение произвольного массива в кучу максимумов называется хипифай.  

• Операция хипифай просеивает элементы вниз, превращая их в кучи.  

• Сложность хипифай составляет O n log n.  

• Для n/2 элементов операция не выполняется, для n/4 элементов выполняется одна операция, и так далее.  

• Пирамидальная сортировка требует O n log n операций, но не требует дополнительной памяти.  

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

• Константа алгоритма хуже, чем у сортировки слиянием или быстрой сортировки.  

• Промахи мимо кэша процессора снижают производительность.  

• Можно ли превратить массив в кучу инплейс?  

• Как искать в словаре по значению, если значения могут повторяться?  

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