Unsorted Insert List implementation of Priority Queue Rewrite implementation of
ID: 3564920 • Letter: U
Question
Unsorted Insert List implementation of Priority Queue
Rewrite implementation of priority queue given in class PriorityQueueL.java with List defined as
private int count;
private List itemList;
(see List.java), so that it uses this unsorted, non-recursive metod insert (it is mandatory thet you use this code with no modifications)
public void insert(int newItem)
{
cnt.incr();
List N = new List();
N.head=newItem;
N.tail=itemList;
itemList=N;
count++;
}
and appropriately modified remove() method that removes the largest element from the priority queue passed to it as the implicit argument.
You may need to implement a method that finds the largest element in a List defined above, first.
After the above modifications, your class PriorityQueueL.java must work as needed when invoked by the sorting method included in class PriorityQueueTestL.java.
In particular, both the sorting and the values of T(n) must be correct.
You are supposed to add to your program any other classes (for instance, cnt.java) that might be necessary; you may re-use them from previous projects if appropriate.
PriorityQueueL.java
--- computed results by your program for arrays (to be sorted) of sizes from 1 to 20, each of which including increasigly sorted, decreasingly sorted, and pseudo-random array, just like the code in classPriorityQueueTestL.java is designed to do.
public class PriorityQueueTestL {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int[] Array;
int N;
for (N = 1; N<=100; N++)
{
Array = new int[N];
for (int i = 0; i < N; i++)
Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
for (int i = 0; i < N; i++)
Array[i] = -i;
// for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
// System.out.println();
cnt.clr(); //counts moves of keys while sorting
Bcnt.clrAll(); //counts comparisons of keys while sorting
PriorityQueueSort(Array);
for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
System.out.println();
// Tcomp(N) is the sorting "time" measured by the number of comparisons
// of keys
System.out.print("Tcomp(" + N +")");
Bcnt.out(" = ");
System.out.print(" " + ( N*(N-1)/2) + " = N*(N-1)/2" + " ");
// Tcall(N) is the sorting "time" measured by the number of calls
System.out.print(" Tcall(" + N +")");
cnt.out(" = ");
System.out.println(" " + (2*N + N*(N-1)/2) + " = 2*N + N*(N-1)/2");
}
}
public static void PriorityQueueSort(int[] A)
{
int n = A.length;
PriorityQueueL PQ = new PriorityQueueL();
for (int i = 0; i < n; i++) PQ.insert(A[i]);
// for (int i = n-1; i >= 0; i--) PQ.insert(A[i]);
// System.out.println("A Size of PQ is " + PQ.Length());
for (int i = n-1; i >= 0; i--) A[i]=PQ.remove();
// for (int i = 0; i < n; i++) A[i]=PQ.remove();
// System.out.println("B Size of PQ is " + PQ.Length());
}
}