Nearly Sorted Algorithm

Nearly Sorted Algorithm

  September 03, 2017    

---

Problem :

you are given an array and k which tells the target position (position in sorted array) is atmost at k distance.

Idea is to use Heap and add first k elements then loop from k to n , pop the sorted one(1st)  and add other elements


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class hackerranksolutionc
 {
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int n=ab.nextInt();
   int k=ab.nextInt();
  // int arr[]=new int[n];
   PriorityQueue<Integer> q=new PriorityQueue<Integer>();
   for(int i=0;i<k;i++)
   q.add(ab.nextInt());
   for(int i=k;i<n;++i)
   {
       System.out.print(q.poll()+" ");
       q.add(ab.nextInt());
   }
   while(!q.isEmpty())
   System.out.print(q.poll()+" ");
   System.out.println();
}
}
}