#13 C++ Жемчужины STD - Операции со стандартными _кучами_
01:04 Введение в кучи -Куча — это структура данных, а не просто распределение памяти. -В C и C++ есть проблемы с именованием, например, std::vector. -Куча обладает полезными свойствами в информатике. 01:02 Свойства кучи -В верхней части кучи всегда находится наибольшее или наименьшее значение. -Вставка и удаление элементов из кучи имеют логарифмическую сложность. -Куча визуализируется как дерево. 02:01 Вставка элементов в кучу -Вставка нового элемента начинается с корня и продолжается сверху вниз. -Новый элемент сравнивается с родительским и меняется местами, если он меньше. -Пример вставки значений 29, «а», 34, 33, 20 иллюстрирует процесс. 03:09 Поведение при вставке -Новый элемент всегда начинается с определённого места. -Сравнение с родительским элементом происходит до тех пор, пока новый элемент не станет меньше родительского. -Поддеревья кучи также являются кучами. 05:11 Логарифмическая сложность -Количество элементов в куче равно 2^d, где d — глубина дерева. -Количество перестановок равно d, что даёт логарифмическую сложность операций. -Куча эффективнее отсортированного диапазона для извлечения наименьшего или -наибольшего элемента. 07:03 Удаление элемента из кучи -Удаление элемента требует изменения конфигурации кучи. -Элемент удаляется, помещается в корень, затем опускается вниз. -Удаление обходится дороже вставки, но всё равно имеет логарифмическую сложность. 08:42 Применение куч -Кучи используются для создания приоритетной очереди. -Приоритетная очередь полезна в играх и других приложениях. -Алгоритм построения траектории по звёздочке требует приоритетной очереди. 09:41 Сортировка по куче -Сортировка по куче основана на свойствах куч. -Кучи можно сохранять в виде вектора. -Индексы дочерних элементов вычисляются путём умножения индекса узла на 2. 10:40 Сопоставление узлов -Первый дочерний элемент равен индексу узла, умноженному на 2. -Второй дочерний элемент равен индексу, умноженному на 2 + 1. -Родитель узла находится путём целочисленного деления индекса на 2. 11:35 Создание кучи -Использование функций push heap и pop heap для работы с кучей. -Создание вектора из 20 элементов со случайными значениями от 0 до 99. -Преобразование вектора в кучу с помощью команды make heap. 12:12 Максимальная и минимальная кучи -По умолчанию make heap создаёт максимальную кучу: первый элемент — самый большой, последующие меньше. -Для создания минимальной кучи требуется компаратор, который можно настроить. -Пример использования компаратора для создания минимальной кучи. 13:11 Проверка кучи -Функция heap until возвращает итератор к первому элементу, который не удовлетворяет требованиям кучи. -Проверка кучности последовательности и определение, до какого момента она остаётся действительной. -Ускорение создания кучи через make heap по сравнению с последовательными вызовами push heap. 15:08 Операция push heap -Вставка элемента в кучу: сначала элемент помещается в конец контейнера, затем вызывается push heap для всего диапазона. -Пример добавления значения 420 в кучу и его распространения до вершины. 17:06 Операция pop heap -Удаление элемента из кучи: обмен местами первого и последнего элементов, восстановление кучи. -Пример удаления элемента 98 из кучи и проверки её состояния после операции. 20:05 Сортировка по кучам -Рекурсивное удаление элементов из кучи до получения отсортированной последовательности. -Реализация сортировки по кучам с помощью цикла. -Использование стандартной функции сортировки кучи из библиотеки. 21:54 Заключение -Подчёркивание простоты и интереса операций с кучей. -Анонс следующего видео о библиотеке алгоритмов и приоритетной очереди.
01:04 Введение в кучи -Куча — это структура данных, а не просто распределение памяти. -В C и C++ есть проблемы с именованием, например, std::vector. -Куча обладает полезными свойствами в информатике. 01:02 Свойства кучи -В верхней части кучи всегда находится наибольшее или наименьшее значение. -Вставка и удаление элементов из кучи имеют логарифмическую сложность. -Куча визуализируется как дерево. 02:01 Вставка элементов в кучу -Вставка нового элемента начинается с корня и продолжается сверху вниз. -Новый элемент сравнивается с родительским и меняется местами, если он меньше. -Пример вставки значений 29, «а», 34, 33, 20 иллюстрирует процесс. 03:09 Поведение при вставке -Новый элемент всегда начинается с определённого места. -Сравнение с родительским элементом происходит до тех пор, пока новый элемент не станет меньше родительского. -Поддеревья кучи также являются кучами. 05:11 Логарифмическая сложность -Количество элементов в куче равно 2^d, где d — глубина дерева. -Количество перестановок равно d, что даёт логарифмическую сложность операций. -Куча эффективнее отсортированного диапазона для извлечения наименьшего или -наибольшего элемента. 07:03 Удаление элемента из кучи -Удаление элемента требует изменения конфигурации кучи. -Элемент удаляется, помещается в корень, затем опускается вниз. -Удаление обходится дороже вставки, но всё равно имеет логарифмическую сложность. 08:42 Применение куч -Кучи используются для создания приоритетной очереди. -Приоритетная очередь полезна в играх и других приложениях. -Алгоритм построения траектории по звёздочке требует приоритетной очереди. 09:41 Сортировка по куче -Сортировка по куче основана на свойствах куч. -Кучи можно сохранять в виде вектора. -Индексы дочерних элементов вычисляются путём умножения индекса узла на 2. 10:40 Сопоставление узлов -Первый дочерний элемент равен индексу узла, умноженному на 2. -Второй дочерний элемент равен индексу, умноженному на 2 + 1. -Родитель узла находится путём целочисленного деления индекса на 2. 11:35 Создание кучи -Использование функций push heap и pop heap для работы с кучей. -Создание вектора из 20 элементов со случайными значениями от 0 до 99. -Преобразование вектора в кучу с помощью команды make heap. 12:12 Максимальная и минимальная кучи -По умолчанию make heap создаёт максимальную кучу: первый элемент — самый большой, последующие меньше. -Для создания минимальной кучи требуется компаратор, который можно настроить. -Пример использования компаратора для создания минимальной кучи. 13:11 Проверка кучи -Функция heap until возвращает итератор к первому элементу, который не удовлетворяет требованиям кучи. -Проверка кучности последовательности и определение, до какого момента она остаётся действительной. -Ускорение создания кучи через make heap по сравнению с последовательными вызовами push heap. 15:08 Операция push heap -Вставка элемента в кучу: сначала элемент помещается в конец контейнера, затем вызывается push heap для всего диапазона. -Пример добавления значения 420 в кучу и его распространения до вершины. 17:06 Операция pop heap -Удаление элемента из кучи: обмен местами первого и последнего элементов, восстановление кучи. -Пример удаления элемента 98 из кучи и проверки её состояния после операции. 20:05 Сортировка по кучам -Рекурсивное удаление элементов из кучи до получения отсортированной последовательности. -Реализация сортировки по кучам с помощью цикла. -Использование стандартной функции сортировки кучи из библиотеки. 21:54 Заключение -Подчёркивание простоты и интереса операций с кучей. -Анонс следующего видео о библиотеке алгоритмов и приоритетной очереди.