Finding the k -largest values in a set of data - Assume you are given a sequence

Question

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> 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.

**********Has to have the following methods!!*********

import java.util.PriorityQueue;

public class KBestCounter> {

PriorityQueue heap;
int k;

public KBestCounter(int k) {
//todo
}

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

public List kbest() {
//todo
}

}

Explanation / Answer

private static int getMax(Integer[] input, int k) { List list = Arrays.asList(input); Set set = new TreeSet(list); list = new ArrayList(set); int value = (list.size() - 1) - k; return list.get(value); } import java.util.PriorityQueue; public class LargestK { private static Integer largestK(Integer array[], int k) { PriorityQueue queue = new PriorityQueue(k+1); int i = 0; while (i

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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