Модуль 21 ⏱ ~9 мин чтения 📐 1 Mermaid диаграмм

2. Задачи Top K

«Не сортируйте всё море данных, если вам нужно лишь зачерпнуть горсть лучших жемчужин».
— Брайан Керниган

Паттерн Top K: Выделение ключевых сущностей

В высоконагруженных бэкенд-системах редко требуется упорядочивать весь массив данных. Бизнес-логика почти всегда оперирует топ-выборками:

  • $10$ наиболее популярных поисковых запросов за последний час (Trending Topics).
  • $5$ ближайших к клиенту курьеров в гео-сервисе (K Closest).
  • $100$ наиболее подозрительных IP-адресов в антифрод-шлюзе (Top K Frequent).

Когда в условии задачи или бизнес-требованиях фигурируют формулировки: «наибольшие», «наименьшие», «наиболее частые» в сочетании с конкретным лимитом $K$, первым выбором инженера должен стать паттерн «Куча размера K».

Наивный подход: Полная сортировка

Интуитивное решение новичка — загрузить все элементы в срез, отсортировать его и взять первые $K$ значений:

Go 
func getTopKNaive(nums []int, k int) []int {
    slices.SortFunc(nums, func(a, b int) int {
        return b - a // Сортировка по убыванию
    })
    return nums[:k]
}

Архитектура решения: Инвертированный выбор кучи

Ключевой математический парадокс паттерна Top K:

  • Для поиска $K$ НАИБОЛЬШИХ элементов используется Min-Heap (Минимальная куча).
  • Для поиска $K$ НАИМЕНЬШИХ элементов используется Max-Heap (Максимальная куча).

Почему для поиска максимумов нужна именно Min-Heap?

Пусть $K = 3$. Мы ищем $3$ наиболее крупных числа в потоке.
Мы инициализируем Min-Heap размера $3$. В корне heap[0] всегда находится наименьший элемент из тройки лидеров (слабейший кандидат в топе).

Когда из потока данных поступает очередной элемент $X$:

  1. Мы сравниваем $X$ с корнем кучи.
  2. Если $X \le \text{корень}$, новый элемент не может претендовать на место в топ-3 — он отбрасывается за $O(1)$.
  3. Если $X > \text{корень}$, слабый кандидат вытесняется (Pop), а $X$ добавляется в кучу (Push), занимая свое место за $O(\log K)$.
flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    Stream["Входящий поток: 8, 2, 10, 5, 15"]:::entry --> Step1["Шаг 1: Накопили 3 элемента (8, 2, 10)<br>Min-Heap: Корень = 2, Дети = 8, 10"]:::process
    Step1 --> Step2{"Пришло число 5:<br>5 > Корень (2)?"}:::warning
    Step2 -->|"Да: Вытеснение"| Heap2["Шаг 2: Pop(2), Push(5)<br>Min-Heap: Корень = 5, Дети = 8, 10"]:::process
    Heap2 --> Step3{"Пришло число 15:<br>15 > Корень (5)?"}:::warning
    Step3 -->|"Да: Вытеснение"| Heap3["Шаг 3: Pop(5), Push(15)<br>Min-Heap: Корень = 8, Дети = 15, 10"]:::success

Mechanical Sympathy: Резидентность в L1-кэше

Оценим алгоритм с точки зрения архитектуры процессора:

  1. Память: Срез кучи имеет фиксированный размер $K$. Для $K = 10$ срез занимает всего $80$ байт.
  2. L1 Data Cache: Этот массив целиком и постоянно находится в сверхбыстром кэше первого уровня L1 ($32\text{–}64\text{ КБ}$).
  3. Отсечение за $O(1)$: Для подавляющего большинства элементов потока условие val <= h[0] вычисляется за $1\text{–}2$ процессорных такта без обращения к системной шине памяти.
  4. Временная сложность: $O(N \log K)$. Поскольку $K \ll N$ (например, $K = 10$, $N = 10^7$), логарифм $\log_2 10 \approx 3.32$ является пренебрежимо малой константой: алгоритм работает практически линейно.

Резюме: Шаблон решения задач Top K

  1. Выбор инварианта: для Top K максимальных — Min-Heap; для Top K минимальных — Max-Heap.
  2. Преаллокация памяти: инициализируйте срез с capacity = K во избежание реаллокаций.
  3. Оптимизация замены: используйте h[0] = val; heap.Fix(&h, 0) вместо связки Pop() + Push().

Перейдем к фундаментальной задаче этого семейства: 3. Kth Largest Element in Array.