Comparing the insertion and removing performance between ALPQueue with HeapPQueue:

Requirements:

1) ( THIS PART IS DONE AND HAS BEEN INCLUDED BELOW) Implement a concrete ALPQueue class (an ArrayList based priority queue) that extends the AbstractPQueue as shown below, along with PQueue.java, ArrayList.java, List.java, PQEntry.java, EntryComparitor.java, and OutOfRangeException.java (any other different queue class implementation will not receive credit).

2) (THIS PART IS MOSTLY DONE. USE SAME CLASSES GIVEN BELOW. MOST OF HeapPQueue HAS BEEN PROVIDED BUT NEEDS TO BE FINISHED) implement a concrete HeapPQueue class (a Heap based priority queue) that extends the AbstractPQueue discussed in the class. Similary, you also need PQueue.java, ArrayList.java, List.java, PQEntry.java , EntryComparitor.java, and OutOfRangeException.java given in the class (any other different queue class implementation, even if it is implemented by yourself, will not receive any credit).

3) Write a performance test program to measure the performance of the above two classes in running time. To do that, you may want to construct two big priority queue instances: one for ALPQueue and one for HeapPQueue. Perform at least 5,000 (random numbers) insert() operations and 5,000 removeMin() operation for each priority queue. Your test program should print out the following information:

ALPQueue:

insert 5000 elements: xxx ms

remove 5000 elements: xxx ms

HeapPQueue:

insert 5000 elements: xxx ms

remove 5000 elements: xxx ms

HEAPPQUEUE

public class HeapPQueue extends AbstractPQueue{

protected ArrayList heap = new ArrayList();

public HeapPQueue() { super(); }

public HeapPQueue(EntryComparator comp) { super(comp); }

protected int parent(int i) { return (i-1)/2; }

protected int left(int i) { return 2*i+1; }

protected int right(int i) { return 2*i+2; }

protected boolean hasLeft(int i) { return left(i)

protected boolean hasRight(int i) { return right(i)

protected void swap(int i, int j) {

try {

PQEntry temp = (PQEntry)heap.get(i);

heap.set(i, heap.get(j));

heap.set(j, temp);

}

catch(OutOfRangeException e) {

System.out.println("OutOfRangeException in swap method");

}

}

public void heapUp(int j) throws OutOfRangeException {

while(j

int k = parent(j);

if(compare(heap.get(j), heap.get(k)) > 0)

swap(k, j);

if(k

break;

j = k;

}

}

public void heapDown(int j) throws OutOfRangeException {

while(hasLeft(j)) {

int leftIndex = left(j);

int smaller = leftIndex;

if(hasRight(j)) {

int rightIndex = right(j);

if(compare(heap.get(leftIndex), heap.get(rightIndex)) > 0)

smaller = rightIndex;

}

if(compare(heap.get(smaller), heap.get(j)) >= 0)

break;

swap(j, smaller);

j = smaller;

} }

public int size() { return heap.size(); }

//THE REST IS GIVEN IN PSUEDO CODE AND NEEDS TO BE IMPLEMENTED FOR THIS

public PQEntry min(){

if(isEmpty())

return null;

otherewise return an A[0] aka the entry at 0

}

public PQEntry insert(Integer key, String value){

PQEntry new item = an entry;

heap.add(heap.size(), new item);

heap.up(heap.size()-1);

return new item;

}

public PQEntry removeMin(){

if(heap.isEmpty())

return null;

if not a case, PQEntry answer = null;

answer = heap.get(0);

swap(0, heap.size()-1);

then heapDown(0);

return answer;

} }

ALPQUEUE: public class ALPQueue extends AbstractPQueue ( private ArrayList list new ArrayListO public ALPQueue superO:) public ALPQuue EntryComparator)super(c):) public int sizereturn list sizeD ) public int findMin i(listsizeO try 1) return min; if comparePEny)listgetfmin), (PQEntry)list.get))>0) return min public PQEntry insert(Integer key, String value) ( PQEntry newest-new PQEntry[key,value) return newest; public PQEntry min0 ifflist.isEmpty0) return null; PQEntry en-null en- (PQEntry)list.getfindMin0) n for min: return en public PQEntry removeMin ifflist.isEmpty0) return null; PQEntry en-null en- (PQEntry)list.remove(findMin) return en ALPQUEUE: public class ALPQueue extends AbstractPQueue ( private ArrayList list new ArrayListO public ALPQueue superO:) public ALPQuue EntryComparator)super(c):) public int sizereturn list sizeD ) public int findMin i(listsizeO try 1) return min; if comparePEny)listgetfmin), (PQEntry)list.get))>0) return min public PQEntry insert(Integer key, String value) ( PQEntry newest-new PQEntry[key,value) return newest; public PQEntry min0 ifflist.isEmpty0) return null; PQEntry en-null en- (PQEntry)list.getfindMin0) n for min: return en public PQEntry removeMin ifflist.isEmpty0) return null; PQEntry en-null en- (PQEntry)list.remove(findMin) return en