Лекция 10. QuickHeap

Показать описание

Андрей Гейн: Часто просят решить такую задачку: дан массив чисел, к которому поступают запросы на добавление чисел, а также на поиск и извлечение минимума среди всех чисел. Эта задача давно и хорошо изучена. Тем интереснее, что меньше десяти лет назад для неё нашлось новое эффективное и очень практичное решение. Мы построим структуру данных, позволяющую добавлять новые элементы за O(1), а извлекать минимум за O(log n). Структура данных называется QuickHeap, но по ходу дела вы также познакомитесь с рандомизированными деревьями поиска и инкрементальной сортировкой. Субъективная сложность лекции — четыре теты из пяти.

Содержание:
1:55 Задача об очереди с приоритетом
8:04 Алгоритм QuickSort
12:59 Алгоритм QuickSelect
17:16 Метод медианы медиан
24:59 Задача об инкрементальной сортировке
31:48 Оценка сложности (осторожно, математика)
39:24 Добавление элементов
48:06 Структура данных QuickHeap
55:15 Рандомизированное бинарное дерево поиска (RBST)
1:00:13 RBST + QuickHeap
1:04:59 Оценка сложности (осторожно, математика)
1:18:23 Амортизационный анализ
1:39:51 Оценка попадания в кэш процессора