TopN

topn.cpp

#include <iostream>
#include <fstream>
#include <queue>
#include <string>
 
using namespace std;
 
void topn(string file_name, int n) {
  ifstream infile(file_name); // open a pointer to the huge file
  int a;
  int *sorted = (int*) malloc(n); // will hold the sorted list in descending order, only for printing purpose
  priority_queue<int, std::vector<int>, std::greater<int> > min_heap; // min heap to store top n numbers
  if(infile.is_open()) {
    while(infile >> a) {
      if(min_heap.size() < n) {
        // if topn doesnt contain n integers we will push just read integer to min heap
        min_heap.push(a);
      } else {
        // if topn already has n integers , push just read integer to min heap and remove the smallest which is the root of min heap
        min_heap.push(a);
        min_heap.pop();
      }
    }
 
    // pop the min heap to sorted in reverse order
    for( int i = n ; i > 0 ; i --) {
      sorted[i] = min_heap.top();
      min_heap.pop();
    }
 
    // print the sorted array
    for( int i = 0 ; i < n ; i++) {
      cout << sorted[i] << endl;
    }
  } else {
    cout << "File not found : " << file_name << endl;
  }
}
 
int main() {
  topn("test.txt", 100);
  return 0;
}