Обработчик и сортировщик потенциально бесконечного потока натуральных чисел

Условие

Дано: Последовательность натуральных чисел, которая может быть бесконечной.

Требуется:

1. Реализовать функцию, принимающую на вход эту последовательность и после просмотра первых n элементов возвращающую не более n уже просмотренных чисел, упорядоченных либо по возрастанию, либо по убыванию.
2. Оценить временную сложность алгоритма в виде O(f(n), m).

Считается, что n значительно превышает m ( n ≫ m > 0 ), а также n ≫ m. Последовательность имеет длину n.

function seq(int $n): Generator
{
    while ($n > 0) {
        yield mt_rand(1, 1000);
        $n--;
    }
}

function solution(Generator $seq, int $n): array
{
}

print_r(solution(seq(1000), 10));

Ответ

Если нужно отсортировать первые n увиденных чисел, считайте не больше n элементов и отсортируйте буфер. Упомянутое m не определено, поэтому задачу top-m нельзя считать заданной автоматически.

function solution(Generator $seq, int $n): array {
    if ($n < 0) throw new InvalidArgumentException();
    $result = [];
    while (count($result) < $n && $seq->valid()) {
        $result[] = $seq->current();
        if (count($result) < $n) $seq->next();
    }
    sort($result, SORT_NUMERIC);
    return $result;
}

Для k = min(n, длина потока) время O(k log k), память O(k). Бесконечность источника не мешает остановке. Если под m подразумевалось число сохраняемых экстремальных элементов среди n, нужна ограниченная куча: O(n log m) времени и O(m) памяти.