THIS IS IMPORTANT TO ME - PLEASE HELP ME WITH THIS JAVA PROGRAMMING - THANK YOU 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. Only one value is provided at a time. The goal is to be able to retrieve the k-largest elements seen so far at any time.

Complete the class KBestCounter<T extends Comparable<? super T>> that keeps track of the k-largest elements seen so far in a stream of data using a priority queue. 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<T> kbest() - return a sorted (in increasing order) list of the k-largest elements. This should run in O(k log k) time. If you run this method twice in a row, it should return the same values. You need to make sure that the priority queue is restored to contain the same elements after the method is called.

We suggest using the built-in java.util.PriorityQueue, which implements a min-heap for you. Do not use the BinaryHeap class provided for this homework assigment, because you will modify this class in problem 2 (and the changes you make could affect the correctness of problem 1). You should never have more than k elements inserted into the Priority Queue at any given time.

You can use the the class TestKBestCounter to test your implementation. However, as always, think about additional test cases you may want to add.

import java.util.PriorityQueue;

import java.util.List;

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

  PriorityQueue<T> heap;

  int k;

  public KBestCounter(int k) {

    //todo

  }

  public void count(T x) {

    //todo

  }

  public List<T> kbest() {

    //todo

    return null; // replace this

  }



}

import java.util.Arrays;

import java.util.List;

public class TestKBestCounter{



  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 [1,2,3]: "+counter.kbest());

    counter.count(2);



    System.out.println("Inserting another 2.");

    System.out.println("5-best should be [1,2,2,3]: "+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 [95,96,97,98,99]: " + 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 [97,98,99,100,101]: " + counter.kbest());

pur-new-sol

Related Questions