Лекция 3. Кучи (начало)

Суббота, 28 сентября 2019
НГУ, ауд. 2128, НГУ, новый корпус

Описание

Понятие очереди с приоритетом. Деревья со свойствами кучи. Почти полные бинарные деревья: нумерация вершин, навигация. Двоичная куча. Операция просеивания вниз и вверх. Реализация операций вставки, удаления и поиска минимума. Сложность операций. Поддержание указателей на элементы кучи. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы. k-ичные кучи, зависимость сложности операций от выбора k

Видео для студентов заочного отделения: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4192/