<?php

/**
 * Дано: последовательность натуральных чисел (потенциально бесконечная).
 *
 * Требуется:
 * 1. Написать функцию, которая принимает на вход эту последовательность
 *    и после обработки n элементов выдаёт не более m наибольших чисел
 *    среди уже обработанных отсортированных в порядке возрастания или убывания.
 * 2. Оценить временную сложность алгоритма как O(f(n, m)).
 *
 * Можно считать что n > 0 и m > 0, a также n >> m.
 */
 
 // Последовательность длины $n
function seq(int $n): Generator
{
    while ($n > 0) {
        yield mt_rand(1, 1000);
        $n--;
    }
}

function solution(Generator $seq, int $m): array
{
    $heap = new SplMinHeap();
    foreach($seq as $el) {
        if($heap->count() === $m) {
            if ($heap->top() >= $el ){
                continue;
            }
            $heap->extract();
        }
        $heap->insert($el);
    }
    $res = array_fill(0, $heap->count(), 0);
    
    for($i=0; !$heap->isEmpty(); $i++){
        $res[$i] = $heap->extract();
    }
    
    return $res;
}

// O((n + m)*log2(m)) - оптимально

// O(n*m + m*log(m) - неоптимально

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