hello-algo/ru/docs/chapter_heap/top_k.md

Задача Top-k

!!! question

Дан неупорядоченный массив `nums` длиной $n$. Необходимо вернуть $k$ наибольших элементов массива.

Для решения этой задачи сначала рассмотрим два метода с более прямолинейным подходом, а затем более эффективное решение с использованием кучи.

Метод 1: обход с выбором

Можно выполнить k раундов обхода, как показано на рисунке ниже, извлекая в каждом раунде 1-й, 2-й, \dots, $k$-й по величине элемент. Временная сложность составляет O(nk).

Этот метод подходит только для случаев, когда k \ll n, поскольку при k, близком к n, временная сложность приближается к O(n^2), что очень затратно по времени.

!!! tip

При $k = n$ мы получаем полную упорядоченную последовательность, что эквивалентно алгоритму «сортировка выбором».

Метод 2: сортировка

Как показано на рисунке ниже, можно сначала отсортировать массив nums, а затем вернуть k крайних правых элементов. Временная сложность составляет O(n \log n).

Очевидно, что этот метод выполняет задачу «с избытком», поскольку нам нужно найти только k наибольших элементов, а не сортировать остальные элементы.

Метод 3: куча

Задачу Top-k можно решить более эффективно с использованием кучи. Процесс показан на рисунке ниже.

1. Инициализируется минимальная куча, элемент на вершине которой является наименьшим.
2. Сначала первые k элементов массива последовательно добавляются в кучу.
3. Начиная с элемента k + 1, если текущий элемент больше элемента на вершине кучи, элемент с вершины извлекается, а текущий элемент добавляется в кучу.
4. После завершения обхода в куче сохраняются k наибольших элементов.

=== "<1>"

=== "<2>"

=== "<3>"

=== "<4>"

=== "<5>"

=== "<6>"

=== "<7>"

=== "<8>"

=== "<9>"

Пример кода приведен ниже:

[file]{top_k}-[class]{}-[func]{top_k_heap}

Всего выполняется n раундов добавления и извлечения элементов, максимальная длина кучи равна k, поэтому временная сложность составляет O(n \log k). Этот метод очень эффективен: при малых k временная сложность стремится к O(n); при больших k временная сложность не превышает O(n \log n).

Кроме того, этот метод подходит для сценариев использования с динамическими потоками данных. При непрерывном добавлении данных можно постоянно поддерживать элементы в куче, обеспечивая динамическое обновление k наибольших элементов.