Алгоритм: Топ-K частых элементов

Решение: Топ-K частых элементов за O(n log k)

Задача

Найти K наиболее часто встречающихся элементов в массиве за время O(n log k) с использованием heap.

Основной подход: Min-Heap (O(n log k))

Алгоритм:

1. Подсчитываем частоту каждого элемента с помощью Counter — O(n)
2. Создаём мин-кучу размером K
3. Итерируем по элементам с их частотами:
   • Если в куче меньше K элементов: добавляем текущий
   • Если куча полна и текущая частота больше минимальной в куче: заменяем минимум
4. Результат: K элементов остаются в куче

Примеры

Анализ сложности

• Time: O(n log k) — n для подсчёта, m log k для операций с heap (m ≤ n уникальных)
• Space: O(n) для Counter + O(k) для heap

Альтернативные подходы

Max-Heap (O(n log n)): Меньше эффективен, но проще когда K близко к количеству уникальных элементов.

Bucket Sort (O(n)): Используем индекс = частота, получаем O(n) временно. Требует O(n) дополнительной памяти.

Практическое применение

• Анализ логов (топ ошибок)
• NLP (частые слова)
• Системы рекомендаций
• Обнаружение аномалий