Categories
Data Structure

Finding Kth Largest/Smallest  Element Using Priority Queue

Explanation: Given an integer K we need to find the largest K elements from the array.

Example: 

Input:

3 5 8 9 10 25 30 1

K = 3

Output:

30 25 10.

Explanation:In here  3 5 8 the first 3 elements ( we picked 3 as k=3) is selected as our initial array.Then we are replacing the first element in the initial array with maximum element in remaining array and continue to replace all the values in initial array with the maximum values in the remaining array. 

3 is replaced with 30

5 is replaced with 25

8 is replaced with 10

//Method Should Be Inside The Class
public static ArrayList<Integer> Largest(int input[], int k) {
		/* Your class should be named Solution
		* Don't write main().
		* Don't read input, it is passed as function argument.
		* Return output and don't print it.
		* Taking input and printing output is handled automatically.
		*/
        
      //PriorityQueue<Integer> Stroing the value PQ
      PriorityQueue<Integer> pq= new  PriorityQueue<Integer> ();
      ArrayList<Integer> result = new ArrayList<>();
      
       //Adding Priority Queue In the integer
      for(int i=0; i<k; i++)
      {
           // adding the values in pq
         pq.add(input[i]);
      }
       
      //Removing the minimum value from the queue
     
    
    // Using the for loop checking whteher values contains in PQ or not
      for(int i=k;i<input.length;i++)
      {   
          //Removing minIndex from arr[i];
       /*   
         int j = pq.remove();
      
         int x = pq.contains(input[j]);
          
          
          if(input[i] < pq.contains(input[j]))
          {
              //Switching the value temp1 with input[i] values
              int temp1 = input[j];
              
              input[i] = k;
              temp1 = input[i];
          }
          
          */
          //Check with input[i] greater than pq.peek();
          //pq.poll() will remove the first element index from the priorirty queue
          //
          if(input[i] > pq.peek())
          {
              pq.poll();
              pq.add(input[i]);
          }
          
          //Not
         
         
         
          
         
      }
        
         while(!pq.isEmpty())
          {
              // Adding result to pq.poll();
              int x = pq.poll();
             
             result.add(x);
          }
        
         return result;
      //Find Our how to evaluate the value through PQ/
    }
    

Leave a Reply

Your email address will not be published.