Алгоритмы и структуры данных поиска: Порядковые статистики. Кучи. Часть 1. Бабенко Максим

Бабенко Максим рассказывает о порядковых статистиках.

1. Нахождение порядковых статистик с помощью рандомизированной модификации алгоритма Quick-Sort.
2. Линейность матожидания времени работы.
3. Приближенные медианы.
4. Выбор k-й порядковой статистики за линейное в худшем случае.
5. Деревья со свойствами кучи.
6. Почти полные бинарные деревья: нумерация вершин, навигация.
7. Двоичная куча.
8. Операция просеивания вниз и вверх.
9. Реализация операций вставки, удаления и поиска минимума.
10. Преобразование произвольного массива ключей в кучу (операция Make-Heap), линейность времени работы.
11. Алгоритм сортировки Heap-Sort.