Структуры данных

Применения кучи: Top-K, Median, Heap Sort

Цели урока

  • Освоить паттерн Top-K
  • Научиться сливать K списков
  • Понять двойную кучу для медианы
  • Реализовать Heap Sort

Предварительные знания

  • Основы кучи
  • Куча (Heap)

Twitter показывает trending topics, Spotify - ваши топ-треки, Google - популярные запросы. Все эти задачи решаются кучей за O(n log k) вместо O(n log n).

  • Twitter/X - trending topics в реальном времени
  • Spotify Wrapped - ваши топ-треки за год
  • Load balancers - выбор наименее загруженного сервера
  • Merge sort для внешней сортировки

Heapsort и расцвет очередей с приоритетом

Куча родилась из задачи сортировки: в 1964 году Дж. У. Дж. Уильямс представил heapsort, а вместе с ним и саму структуру binary heap, которую тут же доработал Роберт Флойд. Очень быстро стало ясно, что куча идеальна как очередь с приоритетом, и она встроилась в классические алгоритмы: Дейкстра и Прим достают следующий узел с минимальным весом именно из кучи. Дальше пошли изящные применения, которые мы разбираем в уроке: поддержание медианы потока двумя кучами (max-heap и min-heap), выбор top-K элементов и моделирование событий по времени (event-driven simulation), где ближайшее событие всегда лежит на вершине. Одна структура, придуманная ради сортировки, стала рабочей лошадкой для целого класса задач.

Паттерн Top-K

**Задача:** найти K наибольших/наименьших элементов.

**Трюк:** для K наибольших используй **min-heap** размера K! Минимум кучи = K-ый наибольший.

**Сложность:** O(n log k) - лучше чем сортировка O(n log n) при k << n.

Для поиска K наибольших элементов используем:

Merge K Sorted Lists

**Задача:** слить K отсортированных списков в один.

**Сложность:** O(n log k), где n - общее число элементов, k - число списков.

Размер кучи при merge K sorted lists:

Streaming Median: Две кучи

**Задача:** находить медиану потока чисел на лету.

**Идея:** две кучи! Max-heap для меньшей половины, min-heap для большей.

**Инвариант:** |small| == |large| или |small| == |large| + 1

Для streaming median нужны:

Heap Sort: O(n log n) in-place

**Heap Sort** - сортировка через кучу. Гарантированно O(n log n), in-place!

СортировкаBestAverageWorstMemory
Quick SortO(n log n)O(n log n)O(n²)O(log n)
Merge SortO(n log n)O(n log n)O(n log n)O(n)
**Heap Sort**O(n log n)O(n log n)O(n log n)O(1)

Heap Sort гарантирует O(n log n) worst-case и O(1) memory. Но на практике Quick Sort быстрее из-за лучшей cache locality.

Heap Sort с гарантированной сложностью O(n log n) и O(1) памятью - лучшая сортировка для общих случаев, и стандартные библиотеки используют именно её.

Std-библиотеки выбирают Timsort, Introsort или Pdqsort. Heap Sort проигрывает на практике из-за плохой cache locality: sift_down прыгает по дереву, разрушая prefetcher.

Big-O говорит, что Heap Sort и Merge Sort одинаковы, и кажется, что O(1) памяти делает Heap Sort абсолютным победителем. Но реальное время определяется кэшем процессора - и здесь предсказуемый последовательный доступ Merge/Quick Sort выигрывает в разы.

Главное преимущество Heap Sort перед Quick Sort:

Паттерны с кучей

  • **Top-K наибольших:** min-heap размера K
  • **Merge K lists:** heap размера K с головами
  • **Streaming median:** две кучи (max + min)
  • **Heap Sort:** O(n log n) worst-case, O(1) memory

Вопросы для размышления

  • Top-K через min-heap размера K - почему именно min-heap, а не max? Какой признак задачи 'top-K' переворачивает ожидаемый тип кучи на противоположный, и где этот же паттерн всплывает в SQL/Spark?
  • Streaming median держит две кучи, балансируя размеры. Какая структура нужна, чтобы поддерживать k-ый перцентиль (а не только median), и почему она не сводится к нескольким кучам?
  • Merge K sorted lists с heap размера K даёт O(n log k). Какие задачи внешней сортировки и обработки больших данных решаются по этому же шаблону - и почему k = число файлов критически влияет на ввод-вывод?

Следующие темы

От деревьев переходим к ещё более гибкой структуре - графам.

  • Введение в графы — Связи между любыми объектами

Связанные уроки

  • ds-14-heaps-intro — Нужно знать heap property и операции перед применениями
  • alg-07-heap-sort — Heap sort - классическое приложение минкучи
  • ds-17-graph-algorithms — Дейкстра использует min-heap как priority queue
  • os-04-scheduling — Priority scheduling в ОС - прямое использование heap
  • alg-01-big-o
Применения кучи: Top-K, Median, Heap Sort

0

1

Войти