Лекция 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 Оценка попадания в кэш процессора