This is java (1) Write a performance driver client program, PQtester.java, that
ID: 3598884 • Letter: T
Question
This is java
(1) Write a performance driver client program, PQtester.java, that uses insert to add N elements to a priority queue, then uses remove the maximum to remove half the keys, then uses insert to fill it up again, then uses remove the maximum to remove all the keys. Use MaxPQ from the algs4.jar.
Write your driver to do this multiple times on random sequences of keys, with N varying from small to large. Do a few runs for each value of N, so you can compute an average, and get a sense of reproducibility. Your driver should measure the time taken for each run, and print-out or plot the average running times. I suggest using System.nanoTime() to capture runtime.
Show your table of run times in the README. What are reasonable values of "small" and "large" values of N?
Explanation / Answer
CODE:
import java.util.Scanner; // scanner class from util pacakage to get values fro keyboard
class PQueue{ /** class Priority Queue **/
int value; // declarion of varaibles
int pri;
public PQueue(int value, int pri) { /** Constructor **/
this.value = value;
this.pri = pri;
}
public String toString() { /** toString() **/
return "Value : "+ value +" Priority : "+ pri;
}
}
class PriorityQueue{ /** Class PriorityQueue **/
private PQueue[] arr; // PQ array declaration
private int arrSize, cap;
public PriorityQueue(int cap) { /** Constructor **/
this.cap = cap + 1; // capacity of PQ array
arr = new PQueue[this.cap];
arrSize = 0;
}
public void delAll() { /** function to delete all elements from PQ **/
arr = new PQueue[cap]; // removing all elements
arrSize = 0;
}
public boolean isEmpty() { /** function to check if PQ is empty or not **/
return arrSize == 0;
}
public boolean isFull() { /** function to check if PQ is full or not **/
return arrSize == cap - 1;
}
public void add(int value, int pri) { /** function to add a value to PQ **/
PQueue pq1 = new PQueue(value, pri);
arr[++arrSize] = pq1; // adding the value and priority into array of type PQ
int p = arrSize;
while (p != 1 && pq1.pri > arr[p/2].pri) { // in respective position , depending on priority
arr[p] = arr[p/2];
p /=2;
}
arr[p] = pq1;
}
public PQueue del(){ /** function to delete value from PQ **/
int p, c;
PQueue it, tem;
if (isEmpty() ){ // checking whether the PQ is empty or not
System.out.println("PQ is empty");
return null;
}
it = arr[1]; // 1st number
tem = arr[arrSize--]; // last number
p = 1;
c = 2;
while (c <= arrSize) {
if (c < arrSize && arr[c].pri < arr[c + 1].pri)
c++;
if (tem.pri >= arr[c].pri)
break;
arr[p] = arr[c];
p = c;
c *= 2;
}
arr[p] = tem;
return it;
}
}
public class PQtester{ /** Class PQtester **/
public static void main(String[] args) { // main method
Scanner s = new Scanner(System.in); // scanner class
System.out.println("Enter Queue size ");
PriorityQueue pqueue = new PriorityQueue(s.nextInt()); // asking user for PQ size and passing to PQ class as constrructor
char c; // variable to ask the user for one more iteration
do { /* Perform Priority Queue operations */
System.out.println("1. Add in PQ"); // menu
System.out.println("2. Remove from PQ");
System.out.println("3. Remove all from PQ");
long startt = System.currentTimeMillis(); // calculation starting time
int ch = s.nextInt(); // getting choice
switch (ch) {
case 1 : System.out.println("Enter Queue value and its priority");
pqueue.add(s.nextInt(), s.nextInt()); // calling functions
break;
case 2 : System.out.println(" Removed a value "+ pqueue.del());
break;
case 3 : System.out.println(" Priority Queue Cleared");
pqueue.delAll();
break;
default :System.out.println("Enter Correct value ");
break;
}
long stopt = System.currentTimeMillis(); // calculating ending time
long et = stopt - startt; // difference between starting and ending time
System.out.println("Time taken for This procedure is "+et); // priting it
System.out.println(" Do you want to continue (Type y or n) ");
c = s.next().charAt(0); // asking user for one more iteration of not
} while (c == 'Y'|| c == 'y');
}// end of main method
}// end of main class
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.