How to find the N longest lines in a text file and print them to stdout?

Question

The first line contains the value of the number "N", followed by several lines. I could solve it in n ^ 2 algorithm order. Can someone suggest a better one?

Answer 1

• You can use a minimal heap and do it in O (n * (log (N))):

     heap = new Min-Heap(N)
     foreach line in text:
          if length(line) > heap.min():
          heap.pop()
          heap.insert(line)
     foreach line in heap:
          print to stdout: line.
  

• it can also be done in O (n) using Select (N) (which selects the Nth number), followed by a section around the Nth number (which orders all sizes with a greater or equal Nth number, one side )

     i = Select(lines, N)
     partition(lines, i)
     for i to size(lines):
           print to stdout: lines[i]