Генерация последовательного файла

Используя кучку Фибоначчи, вы можете сделать это в O(n + (n-k) log k), что равно O(n log k) для малой k, для k, близкой к n, это становится O(n).

Алгоритм: на самом деле вам нужно:

• n вставляет в кучу
• n-k удаления
• n-k findmax's

Сколько стоят эти операции в кучи Фибоначчи ? Вставка и findmax - O(1), амортизация - O(log n). Итак, мы имеем

O(n + (n-k) log k + (n-k)) = O(n + (n-k) log k)