10 максимальных элементов

Цитата esperanto, 10.09.03, 14:28:54

1) строим кучу   0(п)

я конечно всё про кучи уже забыл, но помоему куча строится посложнее.

Цитата esperanto, 10.09.03, 17:08:04

какой проход в сортировке ставками и почему после первого и какова сложность и кажись не правильно

Во, блин, написал. Самому непонятно. Попробую еще раз.
Для каждого элемента большого массива делаем вставку в маленький.
Сложность O(m*n)

Кстати, построение пирамиды O(n*log(n))

У меня есть файл со строками формата:
поле1|поле2|поле3|поле4|поле5|
Пример:
12|34|54|89|54|
13|67|70|3|88|
и т.д....

И мне из этого файла надо было отобрать 10 строк с
самыми максимальными элементами в поле5.
Вот мое решение на Perl
функция получает ссылку на массив в который заранее был прочитан файл
и возвращает ссылку уже на искомый массив.
Пожалуста подскажите можно ли эту функцию оптимизировать (решения только на Perl)
Главное вникните в суть задачи

sub Get10Max {

     my ($r_data) = @_;#ссылка на массив
     my (@tmp_max) = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);#заполнили временный массив
     my (@max);#а вот сюда в конце и попадут 10 макс
     my ($i, $tmp_var);
     my $best = $tmp_max[0];#
     
     for $i(0..$#$r_data) {
           $tmp_var = (split(/\|/, $r_data->[$i]))[4];#выдернули последнее число из строки массива
           my ($m, $min, $index, $flag);
           $flag = 0;
           if ($tmp_var > $best) {#маленький массив сортируем
                       # только когда текущий элемент из большого больше мин из маленького
              $min = $tmp_max[0];
              for $m(0..$#lider) {
                    if ($min > $tmp_max[$m]) {
                         $min = $tmp_max[$m];
                         $index = $m;
                    }
              }
           $flag = 1;#нашли мин
           $best = $min;#для следующего цикла
           }
           if ($flag) {
              $tmp_max[$index] = $tmp_var;#этот массив мы сортируем
              $max[$index] = $i;#мне нужны строки а не
                       #отдельные эл поэтому запоминаем индексы большого массива
           }
     }
     $i = 0;
     for $i(0..$#max) {
           $max[$i] = $r_data->[$max[$i]];#вставляем полные строки из большого массива
     }
     undef $r_data;
     undef @tmp_max;

     return \@max;
}

Цитата wormball, 10.09.03, 17:25:43

я конечно всё про кучи уже забыл, но помоему куча строится посложнее.

Я по кучам специалист! зы

и все таки за линейное время

Цитата esperanto, 10.09.03, 21:45:40

Я по кучам специалист! зы

и все таки за линейное время

Алгоритм+анализ, плз!

1)  троим кучу по известному алг-му binary heap 0(n) (есть в инете)
2) удаляем из кучи 10 раз минимальный эл-т 10*log(n)

-------
O(n+lg(n)) ==> 0(n)

Понял, я с деревьями попутал  :(.
Но при простом выборе максимального имеем те же 10*O(n) = O(n)