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

493

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

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