Please read carefully, will rate. THE METHODS BELOW NEED TO BE USE Finding the k

Question

Please read carefully, will rate.

THE METHODS BELOW NEED TO BE USE

Finding the k-largest values in a set of data - Assume you are given a sequence of values. We do not know how many elements there are in this sequence. In fact, there could be infinitely many. Implement the class KBestCounter<T extends Comparable <? super T>> that keeps track of the k-largest elements seen so far in a set of data. The class should have two methods:

public void count(T x) - process the next element in the set of data. This operation should run in the at worst O(log k) time.

public List kbest() - return a sorted (largest to smallest) list of the k largest elements. This should run in O(k log k) time. The method should restore the priority queue to its original state after retrieving the klargest elements. If you run this method twice in a row, it should return the same values.

Use a Priority Queue to implement this functionality. We suggest using the built-in java.util.PriorityQueue, which implements a min-heap for you. You should never have more than k elements inserted into the Priority Queue at any given time.

import java.util.PriorityQueue;

public class KBestCounter<T extends Comparable <? super T>> {

PriorityQueue heap;
int k;

public KBestCounter(int k) {
//todo
}

public void count(T x) {
//todo
}

public List kbest() {
//todo
}

}

An example illustrates how KBestCounter could be used in this attached tester class:

Explanation / Answer

hey heres the code:

import java.util.*;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MaxHeap_PQ {

PriorityQueue<Integer> pq;


  public MaxHeap_PQ(int i) {
   pq = new PriorityQueue<Integer>(i, new Comparator<Integer>() {


    @Override
    public int compare(Integer o1, Integer o2) {
     // TODO Auto-generated method stub
     return o2 - o1;
    }
   });
  }

  public void insert(int[] x) {
   for (int i = 0; i < x.length; i++) {
    pq.offer(x[i]);
   }
  }


  public int extractMax() {
   return pq.poll();
  }


  public void display() {
   System.out.println(pq);
  }


  public int getSize() {
   return pq.size();
  }

  public void print() {
   System.out.println(pq);
  }

public static void main(String[] args) {

    Scanner s=new Scanner(System.in);
    int l=0,i;
    System.out.println("enter number of elements");

    int n=s.nextInt();

    int arr[]=new int[1000];

    System.out.println("enter elements");

    for(i=0;i<n;i++){//for reading array
        arr[i]=s.nextInt();
       l++;
    }

   MaxHeap_PQ heap = new MaxHeap_PQ(l);
   heap.insert(arr);
System.out.println("How many large values you want to print? ");
n=s.nextInt();
System.out.println(n+" best values are : ");
for(i=0;i<n;i++)
System.out.println(heap.extractMax());
while(true)
{
System.out.println("Want to add elements? (y or n): ");
char c = s.next().charAt(0);
if(c=='y')
{
System.out.println("enter number of elements");
n=s.nextInt();
int k=n+l;
System.out.println("enter elements : ");
    for(i=l;i<k;i++){//for reading array
        arr[i]=s.nextInt();
        l++;
       
}
heap.insert(arr);
System.out.println("How many large values you want to print? ");
n=s.nextInt();
System.out.println(n+" best values are : ");
for(i=0;i<n;i++)
System.out.println(heap.extractMax());
}
else
break;
}
System.out.println("Thankyou!");
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.