# Задача Top-k

!!! question

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

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

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

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

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

![Обход для поиска k наибольших элементов](../assets/top_k_traversal.png)

!!! tip

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

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

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

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

![Сортировка для поиска k наибольших элементов](../assets/top_k_sorting.png)

## Метод 3: куча

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

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

=== "<1>"
    ![Поиск k наибольших элементов с использованием кучи](../assets/top_k_heap_step1.png)

=== "<2>"
    ![top_k_heap_step2](../assets/top_k_heap_step2.png)

=== "<3>"
    ![top_k_heap_step3](../assets/top_k_heap_step3.png)

=== "<4>"
    ![top_k_heap_step4](../assets/top_k_heap_step4.png)

=== "<5>"
    ![top_k_heap_step5](../assets/top_k_heap_step5.png)

=== "<6>"
    ![top_k_heap_step6](../assets/top_k_heap_step6.png)

=== "<7>"
    ![top_k_heap_step7](../assets/top_k_heap_step7.png)

=== "<8>"
    ![top_k_heap_step8](../assets/top_k_heap_step8.png)

=== "<9>"
    ![top_k_heap_step9](../assets/top_k_heap_step9.png)

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

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

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

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