Семинар 7. Хеширование, итераторы (Алгоритмы и структуры данных, часть 1)

Построение совершенной хеш-функции с помощью универсального семейства: графовый метод. Полиномиальное хеширование строк ограниченной длины, почти универсальность.

Концепция итератора и ручки(handle) для элементов в контейнере. Инвалидация ручек. Ручка = указатель в связном списке и дереве. Сложность задания хороших ручек в массиве.

Решение задачи о максимуме в скользящем окне при помощи бинарной кучи. Номер во входном массиве как ручка. Инкапсулированный вариант бинарной кучи: нумерация добавляемых элементов (выдача ID) и использование ID в качестве ручек. Поддержка двустороннего соответствия между ID и номерами в куче.

Семинар №7 в курсе "Алгоритмы и структуры данных, часть 1", осень 2018 (Новосибирск)
Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов
Страница лекции на сайте CS центра: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4280/
Все видео курса по порядку: https://www.youtube.com/playlist?list=PLlb7e2G7aSpSvqoUtSFrhZ-wAyfrQ9lMd

Видео Семинар 7. Хеширование, итераторы (Алгоритмы и структуры данных, часть 1) канала Computer Science Center