Answer:
See explaination
Explanation:
/**KBestCounter.java**/
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class KBestCounter<T extends Comparable<? super T>>
{
PriorityQueue heap;
int k;
public KBestCounter(int k)
{
heap = new PriorityQueue < Integer > ();
this.k=k;
}
//Inserts an element into heap.
//also takes O(log k) worst time to insert an element
//into a heap of size k.
public void count(T x)
{
//Always the heap has not more than k elements
if(heap.size()<k)
{
heap.add(x);
}
//if already has k elements, then compare the new element
//with the minimum element. if the new element is greater than the
//Minimum element, remove the minimum element and insert the new element
//otherwise, don't insert the new element.
else if ( (x.compareTo((T) heap.peek()) > 0 ) && heap.size()==k)
{
heap.remove();
heap.add(x);
}
}
//Returns a list of the k largest elements( in descending order)
public List kbest()
{
List al = new ArrayList();
int heapSize=heap.size();
//runs O(k)
for(int i=0;i<heapSize;i++)
{
al.add(0,heap.poll());
}
//Restoring the the priority queue.
//runs in O(k log k) time
for(int j=0;j<al.size();j++) //repeats k times
{
heap.add(al.get(j)); //takes O(log k) in worst case
}
return al;
}
}
public class TestKBest
{
public static void main(String[] args)
{
int k = 5;
KBestCounter<Integer> counter = new KBestCounter<>(k);
System.out.println("Inserting 1,2,3.");
for(int i = 1; i<=3; i++)
counter.count(i);
System.out.println("5-best should be [3,2,1]: "+counter.kbest());
counter.count(2);
System.out.println("Inserting another 2.");
System.out.println("5-best should be [3,2,2,1]: "+counter.kbest());
System.out.println("Inserting 4..99.");
for (int i = 4; i < 100; i++)
counter.count(i);
System.out.println("5-best should be [99,98,97,96,95]: " + counter.kbest());
System.out.println("Inserting 100, 20, 101.");
counter.count(100);
counter.count(20);
counter.count(101);
System.out.println("5-best should be [101,100,99,98,97]: " + counter.kbest());
}
}
