Question

Problem 2 - K-Best Values - 30 points Find the k-best (i.e. largest) values in a set of data. Assume you are given a sequence of values, one value at a time. We do not know how many elements there are in this sequence. In fact, there could be infinitely many. Implement the class KBestCounter> implements KBest that keeps track of the k-largest elements seen so far in a sequence of data. The class should have two methods: public void count(T x) - process the next element in the set of data. This operation must run in at worst O(log k) time. public List kbest() - return a sorted (smallest to largest) list of the k-largest elements. This must run in at worst O(k log k) time. The method must not clobber the state of your class. This means that if you run this method twice in a row, it should return the same values. Your KBestCounter.java class must implement the provided interface KBest.java. Use a priority queue to implement this functionality. We suggest using the built-in java.util.PriorityQueue. As always, feel free to implement your own tester file to ensure proper functionality.

Answer 1

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());

}

}