How to find 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 multiple lines. I could solve it in order of n^2 algorithm. Can someone suggest a better one?

Answer 1

1. You can use a minimum-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.
   

2. it could also be done in O(n) using Select(N) (which selects the Nth number) followed by partition around the Nth number (which arranges all the with size larger or equal to the Nth number to one side of it).

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